(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
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.
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