Van Emde-Boas priority queue
From Wikipedia, the free encyclopedia
In computer science, a van Emde-Boas priority queue is an an efficient implementation a priority queue 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.
[edit] References
- 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.
- Gaston H. Gonnet and Ricardo Baeza-Yates, Handbook of Algorithms and Data Structures — in Pascal and C, 2nd edition, Addison-Wesley, 1991.
- Paul E. Black, van Emde-Boas priority queue at the NIST Dictionary of Algorithms and Data Structures.
