Evaluating Lists, Heaps, and Splay Trees for Priority Queues.

We describe algorithms for priority queues, including improvements to the top-down splay tree, and detail the results of hold- model experiments performed on a Sun 3/260 workstation and on a Vax 11-785. Heaps and lists perform significantly better than indicated by a previous study. Experience with priority queue algorithms in four actual event-driven simulators gives timings that differ from the hold-model predictions; an examination of simulator event queue activity traces explains the discrepancy. We propose an extension to the hold model and show experiments in which the new model gives better predictions. The conclusion states rules of thumb and a suggested approach for choosing a priority queue implementation suited to a particular application.