Calendar Queues: A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem
Brown, Randy
Abstract
| 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(Z) 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
pending event set
discrete event simulation
priority queue
calendar queue
Notes
Related Papers
Bibtex
@ARTICLE {brown_calendar88,
author = {Randy Brown},
title = {Calendar Queues: A Fast {O}(1) Priority Queue Implementation for the Simulation Event Set Problem},
journal = {Communications of the ACM},
volume = {31},
number = {10},
month = {Oct},
pages = {1220 -- 1227 },
year = {1988}
}