NIST

van Emde-Boas priority queue

(data structure)

Definition: An efficient implementation of priority queues where insert, delete, get minimum, get maximum, etc. take O(log log N) time, where N is the total possible number of keys. Depending on the circumstance, the implementation is null (if the queue is empty), an integer (if the queue has one integer), a bit vector of size N (if N is small), or a special data structure: an array of priority queues, called the bottom queues, and one more priority queue of array indexes of the bottom queues.

Generalization (I am a kind of ...)
priority queue.

Aggregate child (... is a part of or used in me.)
bit vector, array.

Note: After [GBY91, pages 216-217].

Author: PEB

More information

P. van Emde-Boas, R. Kass, and E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Mathematical Systems Theory, 10:99-127, 1977.
P. van Emde-Boas, Preserving Order in a Forest in Less than Logarithmic Time and Linear Space, Inf. Proc. Letters, 6(3):80-82, June 1977.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 August 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "van Emde-Boas priority queue", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/vanemdeboas.html