Boost logo

Boost :

Subject: [boost] [heap] van Emde Boas tree proposal
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2013-05-22 03:30:40

Hi everyone,

I propose to add the van Emde Boas tree (vEBt) to Boost, primarily as a
container adaptor to satisfy the Boost.Heap concept and interface.


The vEBt is an extremely efficient data structure for satisfying the
operations of a priority queue. Where u = |U| and U is the universe of
numbers that can be stored in the container, the vEBt performs top() in
O(1) and push(), pop(), erase() in O(lg lg u). U is, however, limited by
type and range: positive integer values from 0 to 2^w (where w is the word
size)*. The naive implementation uses an abysmal Θ(u) space but this can
be improved to Θ(n) with hashing.


If people support the idea of the vEBt in principle then I would be really
interested in their thoughts on ... should u be a run-time or compile-time
constant? Should the vEBt be available as a data structure for purposes
other than a priority queue?


I recently finished the basic implementation of the algorithm, so anyone
interested in seeing a teething new-born is welcome to take a look.**
 Gritty questions and constructive criticism about class structure, etc are
always welcome. The code won't meet all the programming guidelines yet,
but don't worry, I have them in mind.



* There is a good lecture on it from MIT here:

Boost list run by bdawes at, gregod at, cpdaniel at, john at