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:

• Besides access to the smallest element, what other operations will you need? - Will you be searching for arbitrary keys, or just searching for the smallest? Will you be deleting arbitrary elements from the data, or just repeatedly deleting the top or smallest element?
• Will you know the maximum size of your data structure in advance, or might an arbitrary number of items be inserted into it? - The issue here is whether you can preallocate space for the data structure.
• Will you be changing the priority of elements already in the queue, or simply inserting and removing them? - Changing the priority of elements implies that we must be able to look up elements in the queue based on their key, in addition to being able to retrieve the largest element.

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

• Sorted array or list - In a sorted array,     it is very efficient to find and (by decrementing the top index) delete the smallest element. However, maintaining sortedness makes the insertion of new elements slow. Sorted arrays are suitable when there will be few insertions into the priority queue.
• Binary heaps - This simple, elegant data structure supports both insertion and extract-min in time each.       Heaps maintain an implicit binary tree structure in an array, such that the key of the root of any subtree is less than that of all its descendents. Thus the minimum key is always at the root of the heap. New keys can be inserted by placing them at an open leaf and percolating the element upwards until it sits at its proper place in the partial order.

  Binary heaps are the right answer whenever you know an upper bound on the number of items in your priority queue, since you must specify the array size at creation time.

• Bounded height priority queue - This array-based data structure permits constant-time insertion and find-min operations whenever the range of possible key values is limited.   Suppose we know that all key values will be integers between 1 and n. We can set up an array of n linked lists, such that the ith list serves as a bucket containing all items with key i. We will maintain a pointer top to the smallest nonempty list. To insert an item with key k into the priority queue, add it to the kth bucket and set . To extract the minimum, report the first item from bucket top, delete it, and move top down if the bucket is now empty.

  Bounded height priority queues are very useful in maintaining the vertices of a graph sorted by degree, which is a fundamental operation in graph algorithms.     Still, they are not as widely known as they should be. They are usually the right priority queue for any small, discrete range of keys.

• Binary search trees - Binary search trees make effective priority queues, since the smallest element is always the leftmost leaf, while the largest element is always the rightmost leaf.     The min (max) is found by simply tracing down left (right) pointers until the next pointer is nil. Binary tree heaps prove most appropriate when you also need to search a dictionary of the values, or if you have an unbounded key range and do not know the maximum priority queue size in advance.
• Fibonacci and pairing heaps - These complicated priority queues are designed to speed up decrease-key operations, where the priority of an item already in the priority queue is reduced. This arises, for example, in shortest path computations whenever we discover a shorter route to a vertex v than we had previously established. Thus v has a higher priority of being accessed next.      

  Properly implemented and used, they lead to better performance on very large computations. Still, they are sufficiently complicated that you shouldn't mess with them unless you really know what you are doing.

Implementations: LEDA (see Section ) 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 http://www.cis.ufl.edu/ 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 for further details.        

XTango (see Section ) 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 ). Algorithm 561 [Kah80] of the Collected Algorithms of the ACM is a Fortran implementation of a heap (see Section ).  

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 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 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 comparisons are necessary [CC92].

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