Class priority_queue (from header <queue>
) provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure. By default, a priority_queue
’s elements are stored in a vector
. When elements are added to a priority_queue
, they’re inserted in priority order, such that the highest-priority element (i.e., the largest value) will be the first element removed from the priority_queue
. This is usually accomplished by arranging the elements in a data structure called a heap (not to be confused with the heap for dynamically allocated memory) that always maintains the largest value (i.e., highest-priority element) at the front of the data structure. We use the Standard Library’s heap algorithms in Section 16.3.12. The comparison of elements is performed with comparator function object less<T>
by default, but you can supply a different comparator.
There are several common priority_queue
operations. Function push
inserts an element at the appropriate location based on priority order of the priority_queue
(implemented by calling function push_back
of the underlying container, which then reorders the elements in priority order. Function pop
removes the highest-priority element of the priority_queue
(implemented by calling function pop_back
of the underlying container after removing the top element of the heap). top gets a reference to the top element of the priority_queue
(implemented by calling function front
of the underlying container). empty
determines whether the priority_queue
is empty (implemented by calling function empty
of the underlying container). size
gets the number of elements in the priority_queue
(implemented by calling function size
of the underlying container).
Figure 15.21 demonstrates the priority_queue
adapter class. Line 9 instantiates a priority_queue
that stores double
values and uses a vector
as the underlying data structure. Lines 12–14 use function push
to add elements to the priority_queue
. The while
statement in lines 19–23 uses function empty
(available in all containers) to determine whether the priority_queue
is empty (line 19). While there are more elements, line 21 uses priority_queue
function top
to retrieve the highest-priority element (i.e., the largest value) in the priority_queue
for output. Line 22 removes the highest-priority element in the priority_queue
with function pop
(available in all adapter classes).
1 // Fig. 15.21: fig15_21.cpp
2 // Standard Library priority_queue adapter class.
3 #include <iostream>
4 #include <queue> // priority_queue adapter definition
5 using namespace std;
6
7 int main()
8 {
9 priority_queue< double > priorities; // create priority_queue
10
11 // push elements onto priorities
12 priorities.push( 3.2 );
13 priorities.push( 9.8 );
14 priorities.push( 5.4 );
15
16 cout << "Popping from priorities: ";
17
18 // pop element from priority_queue
19 while ( !priorities.empty() )
20 {
21 cout << priorities.top() << ' '; // view top element
22 priorities.pop(); // remove top element
23 } // end while
24
25 cout << endl;
26 } // end main
Popping from priorities: 9.8 5.4 3.2