11.2 The priority queue Operations

A priority queue is a data structure that can hold elements of type T and implement the five operations given in Table 17:

Table 17 -- Priority queue operations

Function	Implemented operation
push(T)	Adds a new value to the collection being maintained
top()	Returns a reference to the smallest element in the collection
pop()	Deletes the smallest element from the collection
size()	Returns the number of elements in the collection
empty()	Returns true if the collection is empty

Elements of type T must be comparable to each other, either through the use of the default less-than 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 chapter. As with all the containers in the Standard Library, there are several 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.

The priority queue datatype 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 C++ Library that can be used to construct priority queues: vectors or deques. By default, a priority_queue will use vector.

The following illustrates the declaration of several priority queues³:

priority_queue< int > queue_one;      //uses vector and less<int>
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);

The queues constructed out of vectors tend to be somewhat smaller, while the 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 generally works 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 Section 11.3 will illustrate this use.

A priority queue is implemented by internally building a data structure called a heap. Abstractly, a heap⁴ is a binary tree in which the value associated with every node is smaller than or equal to the value associated with either child node.