the vEB tree uses O(u log(u)) bits, but O(u) bits is possible with the same time complexity
idea: use the vEB tree only as adjacency and attach binary heaps at the bottom (using a composed local/global approach)
therefore only manage an universe of u/log(u) by the vEB tree and manage the rest inside binary search trees, each of size log(u), supporting all operations in O(log log u)
overall, all operations remain within their nice time complexity of O(log log u) or even O(1) while only using O(u) bits
Suggested Solution:
combine an in-order, bitwise binary search tree with the vEB tree data structure (note: binary search trees support all operations in a time complexity of O(log n) and use O(n) bits storage for managing up to n items having ids within [1, n])
therefore create a new local/global structure on top of the vEB tree, using the vEB as global and binary search trees as locals
the combined structure has u/log(u) children, each responsible for max. log(u) elements which requires only O(log u) bits and supports all operations in O(log log u) time
this results in a data structure with O(u/log(u) * log(u)) = O(u) bits that still supports all operations in O(log log u) time
unfortunately there's no out-of-the-box bitwise binary search tree in C#, so let's implement our own as follows:
keep track of inserted items by stroring a single bit for each item, telling whether an item is inserted or not
use the item's numeric value as index to address its bit in a bit vector (of length n) -> only O(n) bits
all items are at the position as if the binary search tree was fully-allocated (regardless of parent node existence) to simplify addressing by indexes
for tree navigation, use an additional adjacency bitvector indicating whether a subtree has any children
with the help of this additional invariant, the tree can be traversed as a usual binary search tree because it is guaranteed that there's at least one child smaller/larger when the adjacency bit is set
also, updating the adjacency bitvector doesn't cause any additional cost exceeding the general O-notation of O(log n) because inserting sets max. O(log n) bits and deleting vanishes max. O(log n) bits (and the bits changed are always located on the deterministic path between tree root and node to be inserted/deleted)
therefore all tree operations can be implemented in O(log n) time and the bitvectors only use O(n) bits which actually provides the structure properties that make the storage-efficient vEB tree structure possible
keep in mind that the binary search tree can only store 2^x - 1 items, given a universe of x bits, so the 0 needs to be handled separately using an extra bit
allocating the locals array uses O(sqrt(u)) time because it sets an array of O(sqrt(u)) local structure entries to null for each pointer
but this exceeds the nice time complexity of the vEB tree of O(log log(u)) by far
Suggested Solution:
allocate the array, but don't set every entry to null pointers, etc.
in each vEB operation, only one local per tree layer is touched, so locals can be pointed to on-the-fly
moreover every insert/delete only creates/deletes max. one local / global node
problem: this kind of allocation requires unsafe memory operations, so it's questionable whether it's even possible in C#
a possible compromise could be only pre-allocating the topmost layers on vEB tree initialization, such that the array size of locals can be seen as a constant (e.g. several hundred items), making the lazy-alloc's time complexity feasible