Optimizing static calendar queues

Abstract

The calendar queue is an important implementation of a priority queue that is particularly useful in discrete event simulators. We investigate the performance of the static calendar queue that maintains N active events. The main contribution of this article is to prove that, under reasonable assumptions and with the proper parameter settings, the calendar queue data structure will have constant (independent of N ) expected time per event processed. A simple formula is derived to approximate the expected time per event. The formula can be used to set the parameters of the calendar queue to achieve optimal or near optimal performance. In addition, a technique is given to calibrate a specific calendar queue implementation so that the formula can be applied in a practical setting.