Home → Magazine Archive → October 1988 (Vol. 31, No. 10) → Calendar queues: a fast 0(1) priority queue implementation... → Abstract

Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem

By R. Brown

Communications of the ACM, Vol. 31 No. 10, Pages 1220-1227
10.1145/63039.63045



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.

The full text of this article is premium content

0 Comments

No entries found