van Emde Boas Priority Queue

about | archive

[ 2007-November-08 07:19 ]

I am taking an Advanced Algorithms course at the moment, and it covered van Emde Boas priority queues. It is a priority queue or an associative array that maps sorted integer keys to values. It performs all operations in at most O(log log n) time, as opposed to O(log n) time for the traditional binary heap priority queue. The catch is that the keys must be limited to a certain range, typically between 0 and some power of 2. As usual, the Wikipedia article is very informative. I decided to implement the van Emde Boas queue in Python to actually understand how it works. It is designed to be executable pseudocode, and not an industrial strength implementation. However, I'm pretty sure it is correct thanks to its fairly extensive tests. It supports insert, delete, find, max, min and predecessor operations. Adding a successor operation is left as an exercise for the reader.