Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem
- 1 October 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 31 (10), 1220-1227
- https://doi.org/10.1145/63039.63045
Abstract
A new priority queue implementation for the future event set problem is described in this article. The new implementation is shown experimentally to be O(1) in queue size for the priority increment distributions recently considered by Jones in his review article. It displays hold times three times shorter than splay trees for a queue size of 10,000 events. The new implementation, called a calendar queue, is a very simple structure of the multiple list variety using a novel solution to the overflow problem.Keywords
This publication has 11 references indexed in Scilit:
- An empirical comparison of priority-queue and event-set implementationsCommunications of the ACM, 1986
- Self-Adjusting HeapsSIAM Journal on Computing, 1986
- Self-adjusting binary search treesJournal of the ACM, 1985
- Self-adjusting binary treesPublished by Association for Computing Machinery (ACM) ,1983
- Analysis of future event set algorithms for discrete event simulationCommunications of the ACM, 1981
- A two-list synchronization procedure for discrete event simulationCommunications of the ACM, 1981
- A comparison of heaps and the TL structure for the simulation event setCommunications of the ACM, 1978
- Description and analysis of an efficient priority queue representationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Event manipulation for discrete simulations requiring large numbers of eventsCommunications of the ACM, 1978
- An efficient data structure for the simulation event setCommunications of the ACM, 1977