[boost] [heap] van Emde Boas tree proposal

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.

Rationale

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.

Design

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?

Implementation

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.

Cheers.

Jeremy

* There is a good lecture on it from MIT here:
https://www.youtube.com/watch?v=AjFtTQevtq0
** https://code.google.com/p/veb-heap/