(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 24 January 2005.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "calendar queue", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 January 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/calendarQueue.html