(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 E. Black.
Entry modified Mon Jan 24 10:38:28 2005.
HTML page formatted Wed Oct 26 09:47:18 2005.
Cite this as:
Paul E. Black, "calendar queue", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/calendarQueue.html
