C++ Priority Queue
In C++, the STL priority_queue provides the functionality of a priority
queue data structure.
A priority queue is a special type of queue in which each element is
associated with a priority value and elements are served based on their
priority.
Priority Queue Data Structure
To learn more about priority queues, visit our Priority Queue Data
Structure.
Create a Priority Queue
In order to create a priority queue in C++, we first need to include
the queue header file.
#include <queue>
Once we import this file, we can create a priority_queue using the
following syntax:
priority_queue<type> pq;
Here, type indicates the data type we want to store in the priority queue.
For example,
// create a priority queue of integer type
priority_queue<int> pq_integer;
// create a priority queue of string type
priority_queue<string> pq_string;
Note: By default, STL priority_queue gives the largest element the highest
priority.
C++ Priority Queue Methods
In C++, the priority_queue class provides various methods to perform
different operations on a queue.
Methods Description
push() inserts the element into the priority queue
pop() removes the element with the highest priority
top() returns the element with the highest priority
size() returns the number of elements
empty() returns true if the priority_queue is empty
Insert Element to a Priority Queue
We use the push() method to insert an element into the priority queue. For
example,
#include<iostream>
#include <queue>
using namespace std;
int main() {
// create a queue of int
priority_queue<int> numbers;
// add items to priority_queue
numbers.push(1);
numbers.push(20);
numbers.push(7);
cout << "Priority Queue: ";
// display all elements of numbers
while(!numbers.empty()) {
cout << numbers.top() << ", ";
numbers.pop();
}
cout << endl;
return 0;
}
Run Code
Output
Priority Queue: 20, 7, 1,
In the above example, we have created a priority_queue of integers
called numbers . Here, we have used the push() method to insert the
following elements into the queue: 1, 20, 7.
numbers.push(1);
Notice that we have pushed elements in random order but when printing
them we get the integers sorted in descending order: 20, 7, 1.
The top of the queue is the maximum element in the queue
since priority_queue is implemented as max-heap by default.
Printing Queue Elements
We cannot iterate through a priority queue like we can with vectors and
other containers.
This is why we have used a while loop and
various priority_queue methods to print its elements in the program above.
while(!numbers.empty()) {
cout << numbers.top() << ", ";
numbers.pop();
}
This is because priority_queue is an STL Container Adapter that provides
restrictive access to make it behave like a standard priority queue data
structure.
So, we print its top and then pop the element repeatedly inside a loop until
the queue is empty.
We will see about pop() , top() and empty() in the coming sections.
Remove element from the Priority Queue
We can remove an element from the priority_queue using
the pop() method. This removes the element with the highest priority.
#include<iostream>
#include <queue>
using namespace std;
// function prototype for display_priority_queue()
void display_priority_queue(priority_queue<int> pq);
int main() {
// create a queue of int
priority_queue<int> numbers;
// add items to priority_queue
numbers.push(1);
numbers.push(20);
numbers.push(7);
cout << "Initial Priority Queue: ";
display_priority_queue(numbers);
// remove element from queue
numbers.pop();
cout << "Final Priority Queue: ";
display_priority_queue(numbers);
return 0;
}
// utility function to dislay priority queue
void display_priority_queue(priority_queue<int> pq) {
while(!pq.empty()) {
cout << pq.top() << ", ";
pq.pop();
}
cout << endl;
}
Run Code
Output
Initial Priority Queue: 20, 7, 1,
Final Priority Queue: 7, 1,
In the above example, we have created a priority_queue of integers
called numbers . Initially, the content of the priority queue is {20, 7, 1} .
We have then used the pop() method to remove the top element:
// pop the top element
numbers.pop();
This removes the element with the highest priority: 20.
Hence, the final queue contains the elements 7 and 1. We print the final
queue using the display_priority_queue() function.
Access Element from the Priority Queue
We access the top element of the priority_queue using the top() method.
#include<iostream>
#include <queue>
using namespace std;
int main() {
// create a priority queue of int
priority_queue<int> numbers;
// add items to priority_queue
numbers.push(1);
numbers.push(20);
numbers.push(7);
// get the element at the top
int top = numbers.top();
cout << "Top element: " << top;
return 0;
}
Run Code
Output
Top element: 20
In the above example, we have inserted elements into priority_queue in
the following order: 1, 20, 7.
Then, we print the top element using:
// returns 20
numbers.top();
Here, 20 has the highest priority, so it is at the top.
Get the size of the Priority Queue
We use the size() method to get the number of elements in
the priority_queue .
#include <iostream>
#include <queue>
using namespace std;
int main() {
// create a priority queue of string
priority_queue<string> languages;
// add items to priority_queue
languages.push("C++");
languages.push("Python");
languages.push("Java");
// get the size of queue
int size = languages.size();
cout << "Size of the queue: " << size;
return 0;
}
Run Code
Output
Size of the queue: 3
In the above example, we have created a priority_queue of strings
called languages and added 3 elements to it.
Then we used the size() method to find the number of elements in the
queue:
int size = languages.size();
Since we have added 3 elements to the queue, languages.size() returns 3.
Check if the Priority Queue is Empty
We use the empty() method to check if the priority_queue is empty. This
method returns:
1 (true) - if the priority queue is empty
0 (false) - if the priority queue is not empty
Example: C++ empty() Method
#include <iostream>
#include <queue>
using namespace std;
int main() {
// create a priority queue of ints
priority_queue<string> languages;
cout << "Is the queue empty? ";
// check if the queue is empty
if (languages.empty()) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
cout << "Pushing elements..." << endl;
// push element into the queue
languages.push("Python");
languages.push("C++");
languages.push("Java");
cout << "Is the queue empty? ";
// check if the queue is empty
if (languages.empty()) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
Run Code
Output
Is the queue empty? No
Popping all the elements
Is the queue empty? Yes
In the above example, we have used the empty() method to determine if
the languages priority queue is empty,
if (languages.empty()) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
Initially, the queue has no elements in it.
So languages.empty() returns true .
We then inserted elements into the queue and used the empty() method
again. This time, it returns false .
Min-Heap Priority Queue
We can also create a min-heap priority_queue that arranges elements in
ascending order. Its syntax is:
priority_queue<type, vector<type>, greater<type>> pq;
For example,
// integers are arranged in ascending order
priority_queue<int, vector<int>, greater<int>> pq_integers;
In this type of priority queue, the smallest element gets the highest priority.
Example: Min-Heap Priority Queue
#include<iostream>
#include <queue>
using namespace std;
int main() {
// create a priority queue of int
// arranges elements in ascending order
priority_queue<int, vector<int>, greater<int>> numbers;
// add items to priority_queue
numbers.push(1);
numbers.push(20);
numbers.push(7);
// print element with highest priority
cout << "Top element: " << numbers.top();
return 0;
}
Run Code
Output
