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
