(data structure)
Definition: A fast priority queue implementation having N buckets each with width w, or covering w time. An item with priority p more than current goes in bucket (p/w)%N. Choose N and w to have few items in each bucket. Keep items sorted within buckets. Double or halve N and change w if the number of items grows or shrinks a lot.
See also bucket sort.
Author: PEB
Randy Brown, Calendar Queues: A Fast 0(1) Priority Queue Implementation for the Simulation Event Set Problem, CACM, 31(10):1220-1227, October 1988.
R. Jain, The Art of Computer Systems Performance Analysis, John Wiley and Sons, Inc., 1996, page 410.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 18 March 2019.
HTML page formatted Mon Mar 25 11:53:34 2019.
Cite this as:
Paul E. Black, "calendar queue", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 18 March 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/calendarQueue.html