A Priority Queue is a variant of a Queue such that it’s elements are ordered based on their priority. C++ has a built-in priority queue data structure in it’s Standard Template Library (STL).
Priority queues are implemented as container adapters in C++.
This means that like other container adapters, they have member functions for the container objects.
Let’s understand how we can use the Priority Queue container in C++ to make our own priority queues.
Create a Priority Queue
We can create a priority queue by declaring a priority queue variable of the type std::priority_queue<type>.
The std:: namespace signifies that this supports STL (Standard Template Library) operations.
NOTE: To use this, we must include the <queue> header file in our program.
Since this is a container of the STL, we must provide the template type for the queue. It could be anything from int, float, char, string, etc.
For example, the following are valid declarations of a priority queue.
|
1 2 3 4 5 |
#include <queue> #include <string> std::priority_queue<int> pq1; std::priority_queue<float> pq2; std::priority_queue<std::string> pq3; |
Common Methods on a Priority Queue
Some of the methods which the priority queue container supports are namely:
- empty() -> Checks if the Priority Queue is empty
- size() -> Returns the number of elements in the Queue
- top() -> Returns the element at the top of the Queue
- push() -> Pushes an element to the bottom of the Queue
- pop() -> Pops the last element from the Queue
Let’s understand the above methods using an example. The below code uses all the above methods involving the priority queue.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <string> #include <queue> using namespace std; void print_pqueue (priority_queue<int> pq) { // Prints the Priority Queue priority_queue<int> copy_q = pq; cout << "Priority Queue : "; while (!copy_q.empty()) { cout << copy_q.top() << " "; copy_q.pop(); } cout << "n"; } int main() { // Program demonstrating use of Priority Queue // methods // Create an empty priority queue of integers priority_queue<int> queue_int; // Is the Queue empty now? Yes! cout << "Is the Queue empty now? : " << (queue_int.empty() ? "Yes" : "No") << endl; // Let's add some elements! cout << "Adding some elements...n"; queue_int.push(100); queue_int.push(200); queue_int.push(400); queue_int.push(50); cout << "Number of elements : " << queue_int.size() << endl; cout << "Top element : " << queue_int.top() << endl << endl; print_pqueue(queue_int); cout << "Popping element from the top...nn"; queue_int.pop(); print_pqueue(queue_int); return 0; } |
Here, we create a priority queue of integers and insert the elements 100, 200, 400 and 50 in order.
Note that since a priority queue has the elements sorted in descending order from the top, the insertion will look like this:
After pushing to the queue, we pop the topmost element from the Queue, i.e, the element with the highest priority.
Therefore, 400 will be popped out, making 200 as the new head of the Queue.
|
1 2 3 4 5 6 7 |
Is the Queue empty now? : Yes Adding some elements... Number of elements : 4 Top element : 400 Priority Queue : 400 200 100 50 Popping element from the top... Priority Queue : 200 100 50 |
This shows how we can use the priority queue container easily. Let us move on to a case where you want to have your own priority scheme.
Implementing our own Comparison function
By default, the C++ priority queue evaluates priority only based on sorted values. We can change this, by implementing our own comparison function!
We can overload the default comparison function, by overloading the STL comparison operator.
For this, we must create a comparison class first. Let us call it CompareClass and then introduce our custom comparison in the operator() block.
This must return a bool, since this is a comparison function, and must also be public.
The code structure will look similar to this. We are now comparing based on the ascending order of values!
|
1 2 3 4 5 6 7 8 9 10 |
// Create a Comparison Class for our // integer priority queue class CompareClass { public: bool operator() (int a, int b) { if (a > b) return true; return false; } }; |
We are still not yet done. We need to make the compiler realize that we are using this new class for our comparison operator.
For that, we will need to add two more parameters to our priority_queue<> STL invocation.
|
1 |
priority_queue<type, vector<type>, CompareClass()> pqueue; |
The second parameter tells the compiler that the queue is implemented as a vector<type>. The third one is our Comparison Class.
We will modify our old code to include these new changes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> #include <string> #include <queue> using namespace std; // Create a Comparison Class for our // integer priority queue class CompareClass { public: bool operator() (int a, int b) { if (a > b) return true; return false; } }; void print_pqueue (priority_queue<int, vector<int>, CompareClass> pq) { // Prints the Priority Queue priority_queue<int, vector<int>, CompareClass> copy_q = pq; cout << "Priority Queue : "; while (!copy_q.empty()) { cout << copy_q.top() << " "; copy_q.pop(); } cout << "n"; } int main() { // Program demonstrating use of Priority Queue // methods // Create an empty priority queue of integers priority_queue<int, vector<int>, CompareClass> queue_int; // Is the Queue empty now? Yes! cout << "Is the Queue empty now? : " << (queue_int.empty() ? "Yes" : "No") << endl; // Let's add some elements! cout << "Adding some elements...n"; queue_int.push(100); queue_int.push(200); queue_int.push(400); queue_int.push(50); cout << "Number of elements : " << queue_int.size() << endl; cout << "Top element : " << queue_int.top() << endl << endl; print_pqueue(queue_int); cout << "Popping element from the top...nn"; queue_int.pop(); print_pqueue(queue_int); return 0; } |
Output
|
1 2 3 4 5 6 7 |
Is the Queue empty now? : Yes Adding some elements... Number of elements : 4 Top element : 50 Priority Queue : 50 100 200 400 Popping element from the top... Priority Queue : 100 200 400 |
Observe that we insert elements based on their increasing order of values now, so the top of the queue is the lowest element.
Thus, we have successfully implemented our own comparison function!
Conclusion
In this article, we looked at the C++ Priority Queue container. We also saw some of the methods involved in manipulating them.
Recommended Read: Hash Tables in C++