Subject: [boost] [heap] van Emde Boas tree proposal
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2013-05-22 03:30:40
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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk