The priority queue is an important data structure that is essential to the design of many system programs, such as operating systems, as well as to the design of many applications, such as simulations. In fact, priority queues must be used whenever events are to be scheduled according to objective criteria. Consequently, the implementation details of a priority queue play an important role in determining the performance of the system where it is used. There are many sequential and parallel implementations of algorithms for building and accessing priority queues. The purpose of this paper is to present an exhaustive study of the different performance measuring methodologies and then to apply those measures in order to evaluate different implementation schemes. The authors look at both the average access times and the worst-case access times (the latter are useful for real-time applications). Their conclusions lead to guidelines for how to choose an implementation for a given application. They use different access patterns and a large number of distributions, and they present extensive experimental results.

The paper is extremely well written. It is mostly self-contained and easy to read, and it provides all of the important results in one place. A fairly exhaustive bibliography enhances its usefulness. It is a must read for anybody who wants to use a priority queue in any application.