Their implementation may have a profound effect on the performance of such applications. In this article, we study the performance of well-known sequential priority queue implementations and the recently proposed parallel access priority queues. To accurately assess the performance of a priority queue, the performance measurement methodology must be appropriate. Our results suggest that the best choice for priority queue algorithms depends heavily on the application. For large queue sized of 5,000 elements or more, the Calendar Queue and the Lazy Queue offer good average access times but have very long worst-case access times.
Tree exhibit the best worst-case access times.
Among the parallel access priority queues tested, the Parallel Access Skew Heap provides the best performance on small shares memory multiprocessors. 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.