Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

Overview

vEB

Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

Supports the following Priority-Queue operations:

Insert(int) insert a positive number, allowed range: [0, u)

Delete(int) deletes a previously inserted number

Succ(int) finds the next larger number that is already stored inside the tree. Note that the parameter of succ doesn't neet to exist inside the tree. Specially, Succ(-1) gives the minimum (smallest stored element) of the tree.

Runtime and Space:

All operations run in O(log log u) time with u being a large integer provided at initialisation providing an upper limit for the allowed numbers to be inserted. Space requirement of the (fully filled with all u elements) tree is O(u), as well as initialisation time.

Current implementation uses lazy initialisation, so the init-time is O(sqrt(u)), and Insert may run slower until all of the substructures of the tree were used at least once. I might add a switch to toggle both modes at some point in the future.

Usage:

github.com/chucnorrisful/vEB

See test/main.go for examples.

Todos:

  • add safety features (member check on insertion, deletion etc.)
  • small optimisations: use bitmasks instead of integer division and mod2 calculations
  • add switch for lazyInit vs. fullInit
  • add sparse-mode: usage of hashmaps instead of arrays in internal structure may yield in massive space savings if inserted elements are sparse in a large universe.
  • add linked-list for nodes of tree: enables Succ, Pred in constant time
  • edit PrioQ protocol to also consume Member, Pred, Min, Max
  • extend to negative numbers
publish a tree-like data structure from a backend to a front-end

tree-publish publish a tree-like data structure from a backend to a front-end. It needs to be a tree in order to publish the data as JSON document. If

Lutz Behnke 0 Dec 20, 2021
Recursively searches a map[string]interface{} structure for another map[string]interface{} structure

msirecurse Recursively searches a map[string]interface{} structure for existence of a map[string]interface{} structure Motivation I wrote this package

Fred Moyer 1 Mar 3, 2022
Exp-tree: go library for parsing expression tree

Vinshop expression tree Exp-tree is go library for parsing expression tree Installation go get -u github.com/vinshop/exp-tree Quick start Format Expre

VinShop 6 May 11, 2022
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 21 Jul 22, 2022
Data Structure Libraries and Algorithms implementation

Algorithms Data Structure Libraries and Algorithms implementation in C++ Disclaimer This repository is meant to be used as a reference to learn data s

Priyank Chheda 636 Jul 20, 2022
Trie data structure implementation in Golang 🌳

Gotri Gotri is an Unicode character based Trie/prefix tree implementation in Go, with the suggestion/auto-complete feature for character searching. Si

Monir Zaman 9 Jun 17, 2022
Disjoint Set data structure implementation in Go

dsu Implementation of the Disjoint-Set data structure. The Disjoint-Set, Also called a Union-Find or Merge-Find set, is a data structure that stores a

Iheb Haboubi 6 Jan 29, 2022
Implementation of the MaxStack Data Structure in Go

MaxStack-Golang Implementation of the MaxStack Data Structure in Go This repository contains the design of a max stack data structure that supports th

Girish P Mallya 0 Nov 10, 2021
Bitset data structure

Your basic bit Set data structure for positive numbers A bit array, or bit set, is an efficient set data structure. It consists of an array that compa

Algorithms to Go 127 Jul 29, 2022
Probabilistic set data structure

Your basic Bloom filter Golang probabilistic set data structure A Bloom filter is a fast and space-efficient probabilistic data structure used to test

Algorithms to Go 73 Jul 6, 2022
Data structure and algorithm library for go, designed to provide functions similar to C++ STL

GoSTL English | 简体中文 Introduction GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more p

stirlingx 692 Aug 8, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Derek Parker 599 Aug 10, 2022
BTree provides a simple, ordered, in-memory data structure for Go programs.

BTree implementation for Go This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure. The API is

Google 2.9k Aug 10, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 651 Aug 2, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 651 Aug 2, 2022
Generates data structure definitions from JSON files for any kind of programming language

Overview Archivist generates data structure definitions from JSON files for any kind of programming language. It also provides a library for golang to

Kingsgroup 45 Jun 28, 2022
A data structure for storing points.

ptree This package provides an in-memory data structure for storing points. Under the hood it stores points in a tree structure where nodes are spatia

Josh 17 Apr 18, 2022
Data structure,Algorithms implemented in Go (for education)

Data structure,Algorithms implemented in Go (for education) List of Content : 1. Math - 2. String - 3. Conversions - 4. Sort - 5. Search - 6. Data str

SkShahriarAhmedRaka 4 Jun 10, 2022
A bloom filter is a probabilistic data structure that is used to determine if an element is present in a set

A Go implementation of a bloom filter, with support for boltdb and badgerdb as optional in-memory persistent storage.

Samsondeen 26 Jul 4, 2022