• *Wellcome Guest This Forum is created to help each other. Join us in our journey.

    * Guest Earn Piont Every Post, like, comment,and etc.

How to use C++ Priority_queue?

C

Chrysanthus Forcha

Guest
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 <iostream>
#include <queue>

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

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<type> queueName;

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

priority_queue<int> pq;

or

priority_queue<char> 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<type, vector<same type>, compare> pq;

An example of this instantiation is:

priority_queue<int, vector<int>, less<int> > pq;

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

priority_queue<int, vector<int> > pq;

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

priority_queue<int, vector<int>, greater<int> > 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<int> 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<int>”, 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<char, vector<char>, greater<int> > 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<char, vector<char>, greater<int> > 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<<ch1<<' '<<ch2<<' '<<ch3<<' '<<ch4<<' '<<ch5<<'\n';

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<int> 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<int> 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<int> 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<int> 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<int> 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 <string>
priority_queue<string> 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>
vector<int> vtr = {10, 30, 20, 50, 40};

priority_queue<int> 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<int, vector<int>, 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<int> 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<int, vector<int>, greater<int> > 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.

Credit to linux
 

Latest threads

Top