next up previous contents index CD CD Algorithms
Next: Suffix Trees and Arrays Up: Data Structures Previous: Dictionaries

Priority Queues



Input description: A set of records with numerically or otherwise totally ordered keys.

Problem description: Build and maintain a data structure for quickly inserting and deleting records, while enabling quick access to the smallest or largest key in the set.

Discussion: Priority queues are useful data structures in simulations, particularly for maintaining a set of future events ordered by time so that we can quickly retrieve what the next thing to happen is. They are called ``priority'' queues because they enable you to retrieve items not by the insertion time (as in a stack or queue), nor by a key match (as in a dictionary), but by which item has the highest priority of retrieval.          

If your application performs no insertions after the first query, there is no need for an explicit priority queue. Simply sort the records by priority and proceed from top to bottom, maintaining a pointer to the last record deleted. This situation occurs in Kruskal's minimum spanning tree algorithm, or when simulating a completely scripted set of events.      

However, if you are mixing insertions, deletions, and queries, you need a real priority queue. The following questions will help select the right one:

Depending upon the answers, you have the following basic priority queue choices:

Implementations: LEDA (see Section gif) provides a complete collection of priority queues in C++, including Fibonacci heaps, pairing heaps, Emde-Boas trees, and bounded height priority queues. Fibonacci heaps are their default implementation.  

SimPack/Sim++ is a library of routines for implementing discrete event simulations, built by Robert Cubert and Paul Fishwick, of the University of Florida.     Priority queues are integral to such simulations, and Sim++ contains implementations of linked, binary, leftist, and calendar heaps [Bro88]. If you need a priority queue to control a simulation, check out tex2html_wrap_inline26520 fishwick/simpack/simpack.html. An associated book [Fis95] describes model design using SimPack.    

Bare bones implementations in C and Pascal of the basic priority queue data structures appear in [GBY91]. Most notable is the inclusion of implementations of exotic priority queues such as P-trees and pagodas. See Section gif for further details.        

XTango (see Section gif) is an algorithm animation system for UNIX and X-windows, that includes animations of such advanced priority queue data structures as binomial and Fibonacci heaps, as well as a spiffy animation of heapsort.    

Many textbooks provide implementations of simple priority queues, including [MS91] (see Section gif). Algorithm 561 [Kah80] of the Collected Algorithms of the ACM is a Fortran implementation of a heap (see Section gif).  

Notes: Good expositions on efficient heap construction algorithms include [Baa88, Ben86, CLR90, Man89, MT90b]. See [GBY91] for a description of several exotic priority queues. Empirical comparisons between priority queue data structures include [Jon86].

Bounded height priority queues are useful data structures in practice, but they do not have good worst-case performance bounds when arbitrary insertions and deletions are permitted. However, von Emde Boas priority queues [vEBKZ77] support tex2html_wrap_inline26522 insertion, deletion, search, max, and min operations where each key is an element from 1 to n.    

Fibonacci heaps [FT87] support insert and decrease-key operations in O(1) amortized time, with tex2html_wrap_inline26526 amortized time extract-min and delete operations. The constant-time decrease-key operation leads to faster implementations of classical algorithms for shortest-paths, weighted bipartite-matching, and minimum-spanning-tree.   In practice, Fibonacci heaps are nontrivial to implement and have large constant factors associated with them. However, pairing heaps have been proposed to realize the same bounds with less overhead. Experiments with pairing heaps are reported in [SV87].   

Heaps define a partial order that can be built using a linear number of comparisons.   The familiar linear-time merging algorithm for heap construction is due to Floyd [Flo64]. In the worst case, 1.625n comparisons suffice [GM86] and tex2html_wrap_inline26528 comparisons are necessary [CC92].

Related Problems: Dictionaries (see page gif), sorting (see page gif), shortest path (see page gif).      

next up previous contents index CD CD Algorithms
Next: Suffix Trees and Arrays Up: Data Structures Previous: Dictionaries

Mon Jun 2 23:33:50 EDT 1997