The Priority Queue Operations

A priority queue is a data structure that can hold elements of type T and that implements the following five operations:

Elements of type T must be comparable to each other, either through the use of the default less than operator (the < operator), or through a comparison function passed either as a template argument or as an optional argument on the constructor. The latter form will be illustrated in the example program provided later in this section. As with all the containers in the Standard Library, there are two constructors. The default constructor requires either no arguments or the optional comparison function. An alternative constructor takes an iterator pair, and initializes the values in the container from the argument sequence. Once more, an optional third argument can be used to define the comparison function.

Initializing Queues from other containers

The priority queue data type is built on top of a container class, which is the structure actually used to maintain the values in the collection. There are two containers in the standard library that can be used to construct priority queues: vectors or deques.

The following illustrates the declaration of several priority queues:

priority_queue< int, vector<int> > queue_one;
 priority_queue< int, vector<int>, greater<int> > queue_two;
 priority_queue< double, deque<double> > 
       queue_three(aList.begin(), aList.end());
 priority_queue< eventStruct, vector<eventStruct> > 
       queue_four(eventComparison);
 priority_queue< eventStruct, deque<eventStruct> > 
       queue_five(aVector.begin(), aVector.end(), eventComparison);
 

Queues constructed out of vectors tend to be somewhat smaller, while queues constructed out of deques can be somewhat faster, particularly if the number of elements in the queue varies widely over the course of execution. However, these differences are slight, and either form will generally work in most circumstances.

Because the priority queue data structure does not itself know how to construct iterators, very few of the algorithms noted in Chapter 13 can be used with priority queues. Instead of iterating over values, a typical algorithm that uses a priority queue constructs a loop, which repeatedly pulls values from the structure (using the top() and pop() operations) until the collection becomes empty (tested using the empty() operation). The example program described in the next section will illustrate this use.

Information on ...

Priority queues are implemented by internally building a data structure called a heap. Abstractly, a heap is a binary tree in which every node possesses the property that the value associated with the node is smaller than or equal to the value associated with either child node.