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.
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 E. Black.
Entry modified 24 January 2005.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "calendar queue", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 24 January 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/calendarQueue.html