How to use C++ Priority_queue?

In C++, a queue is a list data structure where the first element to be put in the list is the first element to be removed, when removal is to take place. A priority queue in C++ is similar, but has some ordering; it is the element with the greatest value that is removed first. The priority queue can still be configured so that it is the element with the least value that is removed first. Any queue must have at least the push() function and the pop() function. The push() function adds a new element at the back. For the normal queue, the pop() function removes the first element ever pushed in. For the priority queue, the pop() function removes the element with the highest priority, which could be the biggest or smallest, depending on the ordering scheme.

In order to use the C++ priority_queue, the program should begin with code like:

#include
#include
using namespace std;

It includes the queue library into the program.

In order to continue reading, the reader should have had a basic knowledge of C++.

Article Content

Introduction - see above
Basic Construction
Important Member Functions
Other Priority Queue Functions
String Data
Other Priority Queue Constructions
Conclusion

Basic Construction

The data structure has to be constructed first before it can be used. Construction here means instantiating an object from the queue class of the library. The queue object must then have a name given to it by the programmer. The simplest syntax to create a priority queue is:

priority_queue queueName;

With this syntax, the greatest value is removed first. An example of the instantiation is:

priority_queue pq;

The vector and the deque are two data structures in C++. A priority_queue can be created with either of them. The syntax to create a priority queue from the vector structure is:

priority_queue, compare> pq;

An example of this instantiation is:

priority_queue, less > pq;

Notice the gap between > and > at the end of the declaration. This is to prevent confusion with >>. The default compare code is “less”, meaning the greatest, and not necessarily the first value, would be removed first. So, the creation statement can simply be written as:

priority_queue > pq;

If the least value is to be removed first, then the statement has to be:

priority_queue, greater > pq;

Important Member Functions

The push() Function
This function pushes a value, which is its argument, into the priority_queue. It returns void. The following code illustrates this:

priority_queue pq;
pq.push(10);
pq.push(30);
pq.push(20);
pq.push(50);
pq.push(40);

This priority_queue has received 5 integer values in the order of 10, 30, 20, 50, 40. If all these elements are to be popped out of the priority queue, then they will come out in the order of 50, 40, 30, 20, 10.

The pop() Function
This function removes from the priority_queue the value with the highest priority. If the compare code is “greater”, then it will remove the element with the smallest value. If called again, it removes the next element with the smallest value of the rest; called again, it removes the next smallest value present, and so on. It returns void. The following code illustrates this:

priority_queue, greater > pq;
pq.push('a'); pq.push('c'); pq.push('b'); pq.push('e'); pq.push('d');

Note that in order to call a member function, the name of the object has to be followed by a dot, and then the function.

The top() Function
The pop() function removes the next value of highest priority, but does not return it, as pop() is a void function. Use the top() function in order to know the value of highest priority that has to be removed next. The top() function returns a copy of the value of highest priority in the priority_queue. The following code, where the next value of highest priority is the least value, illustrates this

priority_queue, greater > pq;
pq.push('a'); pq.push('c'); pq.push('b'); pq.push('e'); pq.push('d');
char ch1 = pq.top(); pq.pop();
char ch2 = pq.top(); pq.pop();
char ch3 = pq.top(); pq.pop();
char ch4 = pq.top(); pq.pop();
char ch5 = pq.top(); pq.pop();
cout<The output is 'a"b"c"d"e'.

The empty() Function
If a programmer uses the top() function on an empty priority_queue, after the successful compilation, he would receive an error message such as:

Segmentation fault (core dumped)

So, always check if the priority queue is not empty before using the top() function. The empty() member function returns a bool, true, if the queue is empty, and false if the queue is not empty. The following code illustrates this:

priority_queue pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.push(i1); pq.push(i2); pq.push(i3); pq.push(i4); pq.push(i5);
while(!pq.empty())

cout << pq.top() << ";
pq.pop();

cout << '\n';

Other Priority Queue Functions

The size() Function
This function returns the length of the priority queue, as the following code illustrates:

priority_queue pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.push(i1); pq.push(i2); pq.push(i3); pq.push(i4); pq.push(i5);
int len = pq.size();
cout << len << '\n';

The output is 5.

The swap() Function
If two priority_queues are of the same type and size, then they can be swapped by this function, as the following code shows:

priority_queue pq1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq1.push(i1); pq1.push(i2); pq1.push(i3); pq1.push(i4); pq1.push(i5);
priority_queue pqA;
int it1 = 1; int it2 = 3; int it3 = 2; int it4 = 5; int it5 = 4;
pqA.push(it1); pqA.push(it2); pqA.push(it3); pqA.push(it4); pqA.push(it5);
pq1.swap(pqA);
while(!pq1.empty())

cout << pq1.top() << ";
pq1.pop();
cout<<'\n';
while(!pqA.empty())

cout << pqA.top() << ";
pqA.pop();
cout<<'\n';

The output is:

5 4 3 2 1
50 40 30 20 10

The emplace() Fuction
The emplace() function is similar to the push function. The following code illustrates this:

priority_queue pq1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq1.emplace(i1); pq1.emplace(i2); pq1.emplace(i3); pq1.emplace(i4); pq1.emplace(i5);
while(!pq1.empty())

cout << pq1.top() << ";
pq1.pop();
cout<<'\n';

The output is:

50 40 30 20 10

String Data

When comparing strings, the string class should be used and not the direct use of the string literals because it would compare pointers and not the actual strings. The following code shows how the string class is used:

#include
priority_queue pq1;
string s1 = string("pen"), s2 = string("pencil"), s3 = string("exercise book"), s4 = string("text book"), s5 = string("ruler");
pq1.push(s1); pq1.push(s2); pq1.push(s3); pq1.push(s4); pq1.push(s5);
while(!pq1.empty())

cout << pq1.top() << " ";
pq1.pop();
cout<<'\n';

The output is:

text book ruler pencil pen exercise book

Other Priority Queue Constructions

Explicit Creation from a Vector
A priority queue can be created explicitly from a vector as the following code shows:

#include
vector vtr = 10, 30, 20, 50, 40;
priority_queue pq(vtr.begin(), vtr.end());
while(!pq.empty())

cout << pq.top() << ";
pq.pop();
cout<<'\n';

The output is: 50 40 30 20 10. This time, the vector header also has to be included. The arguments for the constructor function take the start and end pointers of the vector. The data type for the vector and the data type for the priority_queue must be the same.

In order to make the least value the priority, the declaration for the constructor would be:

priority_queue, greater>int> > pq(vtr.begin(), vtr.end());

Explicit Creation from an Array
A priority queue can be created explicitly from an array as the following code shows:

int arr[] = 10, 30, 20, 50, 40;
priority_queue pq(arr, arr+5);
while(!pq.empty())

cout << pq.top() << ";
pq.pop();
cout<<'\n';

The output is: 50 40 30 20 10. The arguments for the constructor function take the start and end pointers of the array. arr returns the start pointer, “arr+5” returns the pointer just past the array, and 5 is the size of the array. The data type for the array and the data type for the priority_queue must be the same.

In order to make the least value the priority, the declaration for the constructor would be:

priority_queue, greater > pq(arr, arr+5);

Note: In C++, the priority_queue is actually called an adaptor, not just a container.

Custom Compare Code

Having all values in the priority queue ascending or all descending is not the only option for the priority queue. For example, a list of 11 integers for a maximum heap is:

88, 86, 87, 84, 82, 79,74, 80, 81, , , 64, 69

The highest value is 88. This is followed by two numbers: 86 and 87, which are less than 88. The rest of the numbers are less than these three numbers, but not really in order. There are two empty cells in the list. The numbers 84 and 82 are less than 86. The numbers 79 and 74 are less than 87. The numbers 80 and 81 are less than 84. The numbers 64 and 69 are less than 79.

The placement of the numbers follow the max-heap criteria - see later. In order to provide such a scheme for the priority_queue, the programmer has to provide his own compare code - see later.

Conclusion

A C++ priority_queue is a first-in-first-out queue. The member function, push(), adds a new value into the queue. The member function, top(), reads the top value in the queue. The member function, pop(), removes without returning the top value of the queue. The member function, empty(), checks if the queue is empty. However, the priority_queue differs from the queue, in that, it follows some priority algorithm. It can be greatest, from first to last, or least, from first to last. The criteria (algorithm) can also be programmer-defined.