Contents
- What is Priority Queue in C++?
- Difference between Priority Queue and Queue
- Syntax of Priority Queue
- Syntax to create min-heap for Priority Queue
- How does c++ Priority Queue work?
- C++ Priority Queue Methods
- Simple programs of Priority Queue
- Conclusion
What is a Priority Queue in C++?
A priority queue in c++ is a type of container adapter, which processes only the highest priority element, i.e. the first element will be the maximum of all elements in the queue, and elements are in decreasing order.
Difference between a queue and a priority queue:
| Priority Queue | Queue |
| Priority Queue container processes the element with the highest priority, whereas no priority exists in a queue. | The queue follows First-in-First-out (FIFO) rule, but in the priority queue highest priority element will be deleted first. |
- If more than one element exists with the same priority, then, in this case, the order of queue will be taken.
Syntax of Priority Queue:
priority_queue<int> variableName;
Note: By default, C++ creates a max-heap for the priority queue.
Syntax to create min-heap for the Priority Queue:
priority_queue <int, vector<int>, greater<int>> q;
Where vector<int> is a STL container and greater<int> is comparator class.
How does c++ Priority Queue work?
Priority Queue considers only the highest priority element.
Inserting elements in a Priority Queue:
/* Program to insert elements in a queue*/
#include<iostream>
#include<queue> //Header-file for queue
using namespace std;
int main()
{
priority_queue<int> p1;
p1.push(35); // inserting element in a queue
p1.push(40);
p1.push(95);
while (!p1.empty())
{
cout << ' ' << p1.top(); //printing elements of queue
p1.pop();
}
}
Accessing elements in a Priority Queue:
/* Program to access an element of highest priority */
#include<iostream>
#include<queue> //Header-file for queue
using namespace std;
int main()
{
priority_queue<int> p1;
p1.push(35);
p1.push(40);
p1.push(95);
p1.push(25);
cout<<p1.top(); //fetch element of highest
priority(maximum element) i.e 95
}
Deleting elements in a Priority Queue:
/* Program to delete elements in a queue*/
#include<iostream>
#include<queue> //Header-file for queue
using namespace std;
int main()
{
priority_queue<int> p1;
p1.push(35);
p1.push(40);
p1.push(95);
p1.push(20);
// queue : 95 40 35 20
p1.pop(); // queue : 40 35 20
p1.pop(); // queue : 35 20
while (!p1.empty())
{
cout << ' ' << p1.top();
p1.pop();
}
}
Learn More C++ Concepts
C++ Priority Queue Methods
Following are the C++ Priority Queue Methods :
| Methods | Description |
| empty() | This method checks whether the priority_queue container is empty or not. If it is empty, return true, else false. It does not take any parameters. syntax : p1.empty() // p1 is priority_queue object |
| size() | This method gives the number of elements in the priority queue container. It returns the size in an integer. It does not take any parameter. syntax : p2.size() // p2 is priority_queue object |
| push() | This method inserts the element into the queue. Firstly, the element is added to the end of the queue, and simultaneously elements reorder themselves with priority. It takes value in the parameter. syntax : p3.push(value) //value to be inserted |
| pop() | This method delete the top element (highest priority) from the priority_queue. It does not take any parameter. syntax : p3.pop() // p3 is priority_queue object |
| top() | This method gives the top element from the priority queue container. It does not take any parameter. syntax : p3.top() |
| swap() | This method swaps the elements of a priority_queue with another priority_queue of the same size and type. It takes the priority queue in a parameter whose values need to be swapped. syntax : p3.swap(p1) |
| emplace() | This method adds a new element in a container at the top of the priority queue. It takes value in a parameter. syntax : p3.emplace(value) |
Lets see the above methods with a simple program :
A Program to show size and empty method:
#include<iostream>
#include<queue> //Header-file for queue
using namespace std;
int main()
{
priority_queue<int> q1;
q1.push(25); //add 25 in a queue
q1.push(15);
q1.push(30);
q1.push(76);
q1.push(85);
// queue : 85 76 30 25 15
cout<<" Number of elements in a priority queue : "<<q1.size()<<endl;
cout<<" The top element is : "<<q1.top()<<endl; //return the maximum element from the queue;
q1.pop(); //remove the highest priority element(MAX element) from the queue;
// queue : 76 30 25 15
q1.push(55);
q1.push(89);
q1.push(35);
cout<<" After Inserting : "<<endl;
//queue : 89 76 55 35 30 25 15
while(!q1.empty())
{
cout<<" "<<q1.top()<<" ";
q1.pop();
}
}
Program of swap method :
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> p1,q1;
//pushing value in p1.
p1.push(28);
p1.push(69);
p1.push(36);
p1.push(23);
p1.push(14);
//pushing value in q1.
q1.push(10);
q1.push(80);
q1.push(32);
q1.push(20);
q1.push(15);
p1.swap(q1);
cout<< "elements in p1 : ";
while(!p1.empty())
{
cout<<" "<<p1.top() <<' ';
p1.pop();
}
cout<< '\n';
cout<< "elements in m1 : ";
while(!q1.empty())
{
cout<<" "<<q1.top() << ' ';
q1.pop();
}
return 0;
}
A Program of embrace method :
#include<iostream>
#include<queue> //Header-file for queue
#include<string>
using namespace std;
int main()
{
priority_queue<string> q1;
q1.emplace("Ankit");
q1.emplace("Ved");
q1.emplace("Nikita");
q1.emplace("Shaurya");
q1.emplace("Anokhi");
// queue: Ved Shaurya Nikita Anokhi Ankit
t
while (!q1.empty())
{
cout<<" "<<q1.top() << " ";
q1.pop();
}
return 0;
}
C++ Program to implement min-heap :
#include<iostream>
#include<queue> //Header-file for queue
using namespace std;
int main()
{
// creates a min heap
priority_queue <int, vector<int>, greater<int> > p1;
p1.push(55);
p1.push(1);
p1.push(76);
p1.push(39);
p1.push(23);
p1.push(49);
p1.push(32);
while (!p1.empty())
{
cout <<" "<< p1.top() << " ";
p1.pop();
}
return 0;
}
Conclusion
Therefore, Priority Queue is a container that stores elements with priority. Unlike queues, which insert or delete the element based on the FIFO rule, in Priority Queue, elements are removed based on priority. The element with the highest priority is the first one to be removed from the queue.
Priority queue supports three operations: is_empty to check if there is no element in the queue,insert_with_priority, to add an element with priority, and Pull_highest_priority_element, to fetch element of highest priority in the queue and show it.
The importance of the priority queue is to process the elements based on priority.
This brings us to the end of the blog on the concept of Priority Queue in C++. We hope that you found this comprehensive and helpful and were able to gain the required knowledge. If you wish to up-skill and learn more such concepts, you can check out the pool of Free online courses on Great Learning Academy.
Also, if you are preparing for Interviews, check out these Interview Questions for C++ to ace it like a pro.
