Introduction to Priority Queue in C++
Priority queues are a special type of queue that behaves as a container, designed specifically in a way where the first element is the greatest of all the elements in the entire queue. All elements are arranged in an order of non-increasing order which means all the elements maintain some synchronization by arranging themselves from increasing to decreasing order. All the elements have a fixed priority or fixed order. Some priority must be given for which it has to be inserted in a queue as mentioned manner of ascending order arrangement. The context of the Priority queue is somewhat like heap as a data structure.
Syntax
Priority _Queue Variable_NameThe syntax follows a way in which the Priority Queue acts as a storage container where the elements will be inserted in an order where the first element to be inserted should be greatest among other elements. It is very much important to include a header file in the program to make use of a priority queue.
How does Priority Queue Work in C++?
Working of Priority Queue can be explained giving a scenario where a container will be taken into consideration where elements will be given as an input to the container in a way where the elements will have an order of non-increasing manner i.e. ascending order. The first element to be inserted should be the greatest because that element will be compared with the other elements and then one element will be returned in a sorted manner. It is very much important to include one header file in the program with respect to the priority queue. Let’s make it more clear suppose we will insert elements like 5,50,14,20,35 in the priority queue or the container then that priority queue will make use of push function and then pop the elements using the pop function with output in a manner 50,35,20,14,5.
But then again one more point comes into the mind like how this sorting of elements is working. Therefore it has to be kept as a point that there is no special algorithm that is being followed but yes priority queue supports heaps as a structure based on how the heap structured in a tree format having the child elements nodes arranged in a heap with respect to parent nodes being divided into 2 parts of Min heap and Max heap respectively.
Methods of Priority Queue in C++
There are some specific methods which are being used are as follows:
1. size()
size() method in C++ will return the actual size of the Priority Queue.
Code:
This program helps to determine the size of the priority queue using size() function.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int sum = 0;
priority_queue<int> pque;
pque.push(10);
pque.push(20);
pque.push(345);
pque.push(312);
pque.push(309);
cout << pque.size();
return 0;
}Output:
2. top()
This method is used to point out the largest of all elements in the priority queue basically for referencing the largest element in the entire queue.
Code:
This program is used to refer to the largest element in the priority queue.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pque;
pque.push(9);
pque.push(11);
pque.push(7);
cout << pque.top();
return 0;
}Output:
3. empty()
This method is used to verify whether the defined container i.e. the priority queue is empty or not. If in case it is not empty it will return a false otherwise it will return a true value.
Code:
This program helps to tell whether the priority queue is empty or not.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pque;
pque.push(20);
if (pque.empty()) {
cout << "True";
}
else {
cout << "False";
}
return 0;
}Output:
4. push()
This method will help in pushing or inserting the elements within the priority queue.
Code:
This program describes the insertion of elements within the priority queue and then displaying the elements.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pque;
pque.push(8);
pque.push(9);
pque.push(1);
pque.push(2);
while (!pque.empty()) {
cout << ' ' << pque.top();
pque.pop();
}
}Output:
5. Pop()
This method helps in removing the top element of the priority queue which is the element with the highest priority.
Code:
This example pops the top element present in the entire queue and it cannot pop any element if empty.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pque;
pque.push(3);
pque.push(4);
pque.push(5);
pque.pop();
pque.pop();
while (!pque.empty()) {
cout << ' ' << pque.top();
pque.pop();
}
}Output:
6. Swap()
If there are two priority queues present and It is a requirement to replace the elements of one priority queue with the elements of another priority queue then that function will be taken as a parameter for the priority queue.
Code:
This program swaps the elements present in one priority queue with the elements present in the other priority queue condition applies that there should be two priority queue present to perform this function.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> mpque1;
priority_queue<int> mpque2;
mpque1.push(8);
mpque1.push(24);
mpque1.push(3);
mpque1.push(6);
mpque2.push(13);
mpque2.push(5);
mpque2.push(37);
mpque2.push(19);
mpque1.swap(mpque2);
cout << "mpque1 = ";
while (!mpque1.empty()) {
cout << mpque1.top() << " ";
mpque1.pop();
}
cout << endl
<< "mpque2 = ";
while (!mpque2.empty()) {
cout << mpque2.top() << " ";
mpque2.pop();
}
return 0;
}Output:
7. Emplace()
This method helps in adding the element on top of the priority queue.
Code:
This program is to illustrate the Emplace function which is used to add some elements on top of the already existing elements within the priority queue and condition applies with a fact that the element gets added on top of the priority queue.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> mpque;
mpque.emplace(3);
mpque.emplace(2);
mpque.emplace(8);
mpque.emplace(9);
mpque.emplace(5);
mpque.emplace(6);
cout << "mpque = ";
while (!mpque.empty()) {
cout << mpque.top() << " ";
mpque.pop();
}
return 0;
}Output:
Conclusion
Priority Queue is a data structure that plays a very pivotal role as it helps the elements get arranged in a sorted manner without using any external sorting algorithm just with the help of internal heap and queue data structure within the container or the queue.
Recommended Articles
This is a guide to Priority Queue in C++. Here we discuss Syntax, how does Priority Queue work in C++ and top methods with examples to implement. You can also go through our other related articles to learn more –
