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.
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
Output
Top element: 1