The priority queue is one of the three container adapters defined in the Standard Library of C++. The other two container adapters are stack and queue. As the name suggests, the priority queue in C++ defines the priority of the elements stored in it. The insertion of elements in the priority queue is similar to the ordinary queue, but the removal of the elements is done according to the priority. So, the element having the highest priority pops out first. In case of multiple elements with the same priority, the element which occurs first will be served first.
To understand the priority queue, let us consider a real-life example. Suppose you have created a to-do reminder list with the tasks that you need to perform in the upcoming week. There might be some tasks that should be prioritized over others. Also, in the middle of the week, the priority of some tasks might change. In such a case, you assign certain priority numbers to each task, and the reminders are generated based on the priority of the tasks.
Difference Between the Ordinary Queue and Priority Queue
Queue and priority queue in C++ share some similar properties, but they differ significantly in their functioning. The following points highlight the key differences between a queue and a priority queue in C++:
- The queue follows the FIFO order, i.e. the first in first out approach. So, the element which is inserted first will be removed first from the queue.
- The priority queue follows the highest priority approach. So, the element with the highest priority will be removed first.
- In the queue, the order in which the elements are inserted is not changed internally and remains the same.
- In the priority queue, the internal order of the elements is changed according to their priorities, using an internal heap structure.
Let us understand the difference between a queue and a priority queue with the help of an example:
Consider the following elements:
50, 100, 20, 300, 10
1. Inserting and deleting the elements in a queue
After inserting the above elements in the order 50, 100, 20, 300, 10, the queue will become:
After insertion
50->100->20->300->10
On applying the pop() operation in the queue, the order of the elements remains the same (FIFO):
After deletion
50
100
20
300
10
2. Inserting and deleting the elements in a priority queue
After inserting the above elements in the order 50, 100, 20, 300, 10, the priority queue will become:
After insertion
50->100->20->300->10
On applying the pop() operation in the priority queue, the element with the highest priority is removed first. The internal heapify method will place the highest priority element at the top:
After deletion
300
100
50
20
10
Syntax of the Priority Queue in C++
The syntax of priority_queue class in C++ is as follows:
template <class type, class Container = vector<type>, class Compare = less <typename Container::value_type> > class priority_queue;
Description of the parameters:
- Type: This is the type of data or elements stored in the priority queue.
- Container: Since the priority queue is a container adapter, it needs an underlying container for its implementation. This parameter specifies the container that is to be used for implementing the priority queue. By default, the vector is used as a standard container.
- Compare: This is an optional parameter. It is an object that determines the internal ordering of the elements in the priority queue. It compares the elements and maintains their relative order. The less <typename> is the default value of the function object, and it returns the same result as the less-than (x < y) operator.
The constructor of the class priority_queue can be used to declare a priority queue in C++ in the following way:
// Syntax to declare a priority queue
priority_queue<int> name_of_queue;
The above expression will create a priority queue named name_of_queue in C++, which will store integer-type elements in it. In C++, an internal heap structure is implemented in the priority queue. By default, a max-heap is maintained in the priority queue, which means the highest priority element will be at the top of the priority queue. A min-heap can also be created by simply specifying the suitable Compare function object.
The following example illustrates the priority queue in C++:
#include <iostream>
#include<queue>
using namespace std;
int main()
{
// declare a priority queue
priority_queue<int> my_queue;
// insert elements in the priority queue
my_queue.push(50);
my_queue.push(100);
my_queue.push(20);
my_queue.push(300);
my_queue.push(10);
cout<<"The elements in the priority queue are: \n";
// print the elements
while(!my_queue.empty())
{
// print the element at the top
cout << my_queue.top(); // highest priority element is at the top
cout << "\n";
// pop the element at the top
my_queue.pop();
}
cout << "\n\n";
return 0;
}
In the above program, a priority queue my_queue is created, which stores integer elements. The elements are inserted in the order: 50, 100, 20, 300, 10. After insertion, the elements are displayed by accessing the element at the top. The element with the highest priority will be at the top (300 in this case).
Member Functions of Priority Queue
Just like the other C++ STL containers, the priority queue also consists of some member functions that you can directly access in your code by adding the header file for the priority queue i.e., #include<queue>. These member functions are mentioned below:
- priority_queue::empty() in C++ STL
- priority_queue::size() in C++ STL
- priority_queue::top() in C++ STL
- priority_queue::push() in C++ STL
- priority_queue::pop() in C++ STL
- priority_queue::swap() in C++ STL
- priority_queue::emplace() in C++ STL
1. priority_queue::empty()
empty() member function of the priority queue is used to determine whether the priority queue is empty or not.
Syntax
priority_queue.empty() //name of the priority queue
//could be anything
Parameters
The empty() function does not accept any parameter or arguments.
Return Value
This member function has a boolean return data type, which means it will return only true or false. If your priority queue is empty, it will return True otherwise you will get False as the return value from the function.
Example
1. Input : my_queue = 3, 0, 2, 5
my_queue.empty();
Output : False
2. Input : my_queue = 0
my_queue.empty();
Output : False
3. Input : my_queue
my_queue.empty();
Output : True
Errors and Exceptions
- If you try to pass an argument to the empty() function, it will throw an error.
- It will not show an exception throw guarantee.
Below is the implementation of the empty() member function of the priority queue:
#include <iostream>
#include <queue>
using namespace std;
//function to check if the priority queue is empty or not
bool example(priority_queue<int> my_queue)
{
if (my_queue.empty()) {
return true;
}
else {
return false;
}
}
int main()
{
//creating a priority queue of integer data type
priority_queue<int> my_queue;
//pushing values in the priority queue
my_queue.push(1);
my_queue.push(2);
my_queue.push(3);
my_queue.push(4);
// priority Queue becomes 4, 3, 2, 1
cout<<example(my_queue);
}
2. priority_queue::size()
The size() member function of the priority queue is used to obtain the size of the priority queue i.e, the total number of elements that are present inside the priority queue.
Syntax
priority_queue.size() //name of the priority queue
//could be anything
Parameters
The size() function does not accept any parameter or arguments.
Return Value
The size() member function has an integer return data type. It returns a single integer that determines the total number of elements that are present inside the priority queue.
Example
1. Input : my_queue = 3, 0, 2, 5
my_queue.size();
Output : 4
2. Input : my_queue = 0
my_queue.size();
Output : 1
3. Input : my_queue
my_queue.size();
Output : 0
Errors and Exceptions
- If you try to pass an argument to the size() function, it will throw an error.
- It will not show an exception throw guarantee.
Below is the implementation of the size() member function of the priority queue:
#include <iostream>
#include <queue>
using namespace std;
//function to determine the size of the priority queue
int example(priority_queue<int> my_queue)
{
return my_queue.size();
}
int main()
{
//creating a priority queue of integer data type
priority_queue<int> my_queue;
//pushing values in the priority queue
my_queue.push(1);
my_queue.push(2);
my_queue.push(3);
my_queue.push(4);
// priority Queue becomes 4, 3, 2, 1
cout<<"Size of the priority queue is: " <<example(my_queue);
}
3. priority_queue::top()
The top() member function of the priority queue is used to get the element having the highest priority in the priority queue container.
Syntax
priority_queue.top() //name of the priority queue
//could be anything
Parameters
The top() function does not accept any parameter or arguments.
Return Value
The top() member function has an integer return data type. It returns a single integer that determines the largest element of the priority queue container.
Example
1. Input : my_queue = 3, 2, 0
my_queue.top();
Output : 3
2. Input : my_queue = 0
my_queue.top();
Output : 0
3. Input : my_queue = 7, 7, 3, 1, 0
my_queue.top();
Output : 7
Errors and Exceptions
- The top() function shows an undefined behavior if the priority queue container is empty.
- It will not show an exception throw guarantee if the priority queue container is empty.
Below is the implementation of the top() member function of the priority queue:
#include <iostream>
#include <queue>
using namespace std;
//function to find the largest element of the priority queue container
int example(priority_queue<int> my_queue)
{
return my_queue.top();
}
int main()
{
//creating a priority queue of integer data type
priority_queue<int> my_queue;
//pushing values in the priority queue
my_queue.push(1);
my_queue.push(2);
my_queue.push(3);
my_queue.push(4);
// Priority Queue becomes 4, 3, 2, 1
cout<<"Largest element of the priority queue is: " <<example(my_queue);
}
4. priority_queue::push()
The push() member function of the priority queue is used to insert an element in the priority queue container. When the element is added to the priority queue container, the size of the container gets increased by 1 automatically. The element is initially inserted at the last, but as the priority queue has a maximum heap internal structure by default, the elements automatically get reordered in descending order.
Syntax
priority_queue.push(element) //name of the priority queue
//could be anything
Parameters
Value: The push() member function accepts a value as its argument that has to be inserted in the priority queue container.
Return Value
This member function does not return any value.
Example
1. Input : my_queue
my_queue.push(1);
my_queue.push(2);
my_queue.push(3);
my_queue.push(4);
my_queue.push(5);
my_queue.push(6);
Output : 6, 5, 4, 3, 2, 1
2. Input : my_queue = 7, 5, 1, 0
my_queue.push(3);
Output : 7, 5, 3, 1, 0
3. Input : my_queue
my_queue.push(5);
Output : 5
Errors and Exceptions
- The push() function throws an error if the data type of the element that is passed to the function does not match with the data type of the priority queue container.
- If the argument does not throw an exception, the function shows no exception either.
Below is the implementation of the push() member function of the priority queue:
#include <iostream>
#include <queue>
using namespace std;
//function to print the elements of the priority queue container
void print(priority_queue<int> my_queue)
{
while(!my_queue.empty())
{
cout << ' ' << my_queue.top();
my_queue.pop();
}
}
int main()
{
//Example 1
//creating a priority queue of integer data type
priority_queue<int> my_queue1;
//pushing values in the priority queue
my_queue1.push(1);
my_queue1.push(2);
my_queue1.push(3);
my_queue1.push(4);
// Priority Queue becomes 4, 3, 2, 1
cout<<"Example 1:";
print(my_queue1);
cout<<endl;
//Example 2
//creating another priority queue of integer data type
priority_queue<int> my_queue2;
//pushing identical values in the priority queue
my_queue2.push(4);
my_queue2.push(4);
my_queue2.push(4);
//Priority Queue becomes 4, 4, 4
cout<<"Example 2:";
print(my_queue2);
cout<<endl;
}
5. priority_queue::pop()
The pop() member function of the priority queue is used to remove the top element of the priority queue container.
Syntax
name_of_priority_queue.pop() //name of the priority queue
//can be anything
Parameters
The pop() function does not accept any parameters.
Return Value
This member function does not return anything.
Example
1. Input : my_queue = 3, 0, 2, 1
my_queue.pop();
Output : 0, 2, 1
2. Input : my_queue = 4, 4, 4
my_queue.top();
Output : 4, 4
3. Input : my_queue = 7, 7, 0, 1, 7
my_queue.top();
Output : 7
Errors and Exceptions
- If you try to pass an argument to the size() function, it will throw an error.
- If the argument does not throw an exception, the function shows no exception either.
Below is the implementation of the pop() member function of the priority queue:
#include <iostream>
#include <queue>
using namespace std;
int main()
{
// creating a priority queue of integer data type
priority_queue<int> my_queue;
my_queue.push(0);
//queue becomes 0
my_queue.push(1);
//queue becomes 1, 0
my_queue.push(2);
// queue becomes 2, 1, 0
my_queue.pop();
// queue becomes 1, 0
my_queue.pop();
// queue becomes 0
// printing the elements of the priority queue container
while (!my_queue.empty()) {
cout << ' ' << my_queue.top();
my_queue.pop();
}
}
6. priority_queue::swap()
The swap() member function of the priority queue is used to swap the elements of one priority queue with the elements of another priority queue. Both the priority queues must have the same data type and size to be eligible for swapping elements. After swapping, the elements are printed in the reverse order since the element present at the top is printed first, and this order is followed further.
Syntax
priority_queue1.swap(priority_queue2) //name of both the priority
//queues could be anything
Parameters
The swap() function accepts the second priority queue that takes part in swapping as its parameter.
Return Value
This member function does not return anything.
Example
1. Input : my_queue1 = {2, 4, 6, 8}
my_queue2 = {1, 3, 5, 7}
my_queue1.swap(mymy_queue2);
Output : my_queue1 = {7, 5, 3, 1}
my_queue2 = {8, 6, 4, 2}
2. Input : my_queue1 = {1, 3, 6, 9}
my_queue2 = {1, 4, 8, 12}
my_queue1.swap(mymy_queue2);
Output : my_queue1 = {9, 6, 3, 1}
my_queue2 = {12, 8, 4, 1}
Errors and Exceptions
- This function will throw an error if the priority queues are of different data types or have different sizes.
- If the argument does not throw an exception, the function shows no exception either.
Below is the implementation of the swap() member function of the priority queue:
#include <iostream>
#include <queue>
using namespace std;
//function to print the elements of the first priority queue
void print_queue1(priority_queue<int> my_queue1)
{
while(!my_queue1.empty())
{
cout<<" "<<my_queue1.top();
my_queue1.pop();
}
cout<<endl;
}
//function to print the elements of the second priority queue
void print_queue2(priority_queue<int> my_queue2)
{
while(!my_queue2.empty())
{
cout<<" "<<my_queue2.top();
my_queue2.pop();
}
cout<<endl;
}
int main()
{
// creating the priority queue of integer data type
priority_queue<int> my_queue1;
my_queue1.push(2);
my_queue1.push(4);
my_queue1.push(6);
my_queue1.push(8);
// creating the priority queue of integer data type
priority_queue<int> my_queue2;
my_queue2.push(1);
my_queue2.push(3);
my_queue2.push(5);
my_queue2.push(7);
//printing the elements before swapping
cout<<"Before Swapping"<<endl;
cout<<"Priority Queue 1: ";
print_queue1(my_queue1);
cout<<"Priority Queue 2: ";
print_queue2(my_queue2);
my_queue1.swap(my_queue2);
//printing the elements after swapping
cout<<"After Swapping"<<endl;
cout<<"Priority Queue 1: ";
print_queue1(my_queue1);
cout<<"Priority Queue 2: ";
print_queue2(my_queue2);
}
7. priority_queue::emplace()
The emplace() member function of the priority queue is used to add a new element to the priority queue container. This element is added at the top of the container. The elements are printed in the reverse order since the element at the top is printed first and the respective order is followed further.
The main difference between the push() function and emplace() function is that the push() function inserts a copy of an object in the queue that already exists while the emplace() function creates a new instance of the class in the container.
Syntax
priority_queue.emplace(element) //name of the priority
//queue could be anything
Parameters
The emplace() function accepts the element that has to be inserted in the priority queue container.
Return Value
This member function does not return anything.
Example
1. Input : my_queue
my_queue.emplace(1);
my_queue.emplace(2);
my_queue.emplace(3);
my_queue.emplace(4);
my_queue.emplace(5);
my_queue.emplace(6);
Output : 6, 5, 4, 3, 2, 1
2. Input : my_queue = 7, 5, 1, 0
my_queue.emplace(3);
Output : 7, 5, 3, 1, 0
3. Input : my_queue
my_queue .emplace(5);
Output : 5
Errors and Exceptions
- This function will throw an error if the argument has a different data type than the data type of priority queue.
- If the argument does not throw an exception, the function shows no exception either.
Below is the implementation of the emplace() member function of the priority queue:
#include <iostream>
#include <queue>
using namespace std;
//function to print the elements of the priority queue container
void print(priority_queue<int> my_queue)
{
while(!my_queue.empty())
{
cout << ' ' << my_queue.top();
my_queue.pop();
}
}
int main()
{
//Example 1
//creating a priority queue of integer data type
priority_queue<int> my_queue1;
//pushing values in the priority queue
my_queue1.emplace(1);
my_queue1.emplace(2);
my_queue1.emplace(3);
my_queue1.emplace(4);
// Priority Queue becomes 4, 3, 2, 1
print(my_queue1);
cout<<endl;
}
Use-Cases of a Priority Queue
The priority queue has several useful applications. Some major applications of the priority queue are discussed below:
- Prim’s Algorithm: This popular algorithm for finding a minimum spanning tree can also be implemented using the priority queue. The priority queue will be used to implement the function for extracting the nodes with the minimum key value.
- Dijkstra's shortest path algorithm: The priority queue can also be used to implement Dijkstra’s shortest path algorithm. The priority queue is used to efficiently extract the vertices with minimum distance in the graph.
- Heap Sort: Heaps are generally used to implement the priority queue. The internal max-heap or min-heap makes the priority queue itself a max-priority-queue or a min-priority-queue, and the elements stored are removed in sorted order.
- Data Compression: A popular data compression technique - Huffman coding can also be implemented using the priority queue. As a max-heap created for taking input in the Huffman Coding technique, a priority queue can be used to achieve this efficiently.
- A* Search algorithm: The A* Search algorithm used in AI can also be implemented using the priority queue. The priority queue is used to store the unexplored routes having the smallest lower bound.
How to Create a Min-Heap for the Priority Queue?
The priority queue in C++ is by default implemented using the internal max-heap structure. However, a min-heap can also be created to implement the priority queue. We will discuss two ways to create a min-heap for the priority queue in C++.
-
Using greater<typename> as the Comparator Function
To create a min-heap, the priority_queue class constructor can be used along with a comparator function. By default, this comparator function is less<typename>which creates a max-heap. For a min-heap, the parameter comparator should be set to greater<typename>.
Syntax
priority_queue <typename, vector<typename>, greater<typename>> name_of_queue;
The following program will illustrate implementation of priority queue in C++ using a min-heap:
#include <bits/stdc++.h>
using namespace std;
int main ()
{
// declare a priority queue using min-heap
priority_queue <int, vector<int>, greater<int>> my_queue;
// insert elements into priority queue
my_queue.push(50);
my_queue.push(100);
my_queue.push(20);
my_queue.push(300);
my_queue.push(10);
cout<<"The elements in the priority queue are: \n";
// print the elements
while(!my_queue.empty())
{
// print the element at the top
cout << my_queue.top(); // element with the highest priority
cout << "\n";
// pop the element at the top
my_queue.pop();
}
cout << "\n\n";
return 0;
}
In the above program, a priority queue my_queue is created which stores integer elements. The elements are inserted in the order: 50, 100, 20, 300, 10. Since it is implemented using the min-heap, the element with the highest priority will be 10 in this case.
-
Using the Default Priority Queue
Another way of creating a min-heap for priority queue in C++ is by using the default priority queue based on max-heap and simply multiplying the elements to be inserted by -1. And while accessing these elements, multiply them again with -1 to get the original values. This method for the creation of a min-heap for priority queue is generally used in competitive programming.
The following program will illustrate this approach for implementing a priority queue using the min-heap:
#include <iostream>
#include <queue>
using namespace std;
int main()
{
// declare the default priority queue
priority_queue<int> my_queue;
// declare array of elements to be inserted
int elements[] = { 50, 100, 20, 300, 10 };
// insert elements into the priority queue
// while multiplying them by -1.
for (int i = 0; i < 5; i++) {
my_queue.push((-1) * elements[i]);
}
// print the elements in the priority queue
cout << "The elements in the min-heap priority queue are:\n";
while (!my_queue.empty()) {
// multiply elements by -1
// to get the original values
cout << my_queue.top() * (-1) << " ";
my_queue.pop();
}
cout << "\n\n";
return 0;
}
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Final Thoughts!
In this article, you learned about the ins and outs of priority queues in C++. You figured out how to use priority queues in real-life, understood the differences between an ordinary queue and a priority queue, and implemented priority using the simplest possible code. Apart from this, you also saw the different member functions of a priority queue in C++ and how to implement each of them. At the end, you learned how to implement a min-heap and explored some real-life use-cases of priority queues.
You can check out our tutorial on C++ Programming for Beginners to get an overview of the c++ concepts.
Why stop here? If you want to land your foot on professional software development and learn trending technologies, check out our course on Full Stack Web Development. This will allow you to prepare for the toughest of interviews with hands-on practical examples. You will understand advanced software development concepts such as DevOps, Agility, Java, CSS, HTML, AWS, etc.
If you want to access well-curated free online courses by top instructors, you must check out the complete list of free online courses by Simplilearn. If you have any queries or suggestions for us you can mention them in the comment box, and our experts will answer them for you as soon as possible. Happy Learning!