Last Updated on 2022-07-19 by Clay
priority_queue is a queue container provided in the C++ Standard Template Library (STL), which returns the element with the highest priority first.
In the general case of storing INT data, the priority of elements is sorted from large to small. Of course we can change the priority definition of priority_queue.
How to use priority_queue
The following is a simplest sample code
push(): Push element into queue.top(): Get the highest priority elementpop(): Pop (delete) the highest priority element
#include <iostream>
#include <queue>
using namespace std;
int main() {
// Init
priority_queue<int> pq;
pq.push(4);
pq.push(9);
pq.push(5);
pq.push(1);
pq.push(6);
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
return 0;
}
Output:
9
6
5
4
1
As you can see, the elements we randomly push into the queue have been sorted in descending order; it means that the larger the value, the higher the priority.
Change the priority rule
The smaller the value, the higher the priority
#include <iostream>
#include <queue>
using namespace std;
int main() {
// Init
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(4);
pq.push(9);
pq.push(5);
pq.push(1);
pq.push(6);
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
return 0;
}
Output:
1
4
5
6
9
This is the most common changes, we can do it directly with greater<int>.
Customize priority rule
If we want:
- The even numbers have higher priority
- The smaller number have higher priority
We can construct our own priority rules in the following way:
#include <iostream>
#include <queue>
using namespace std;
template <typename T>
class cmp {
public:
bool operator()(T a, T b) {
if (a % 2 == 1 && b % 2 == 0) {
return true;
}
else if (a % 2 == 0 && b % 2 ==1) {
return false;
}
else {
return a > b;
}
}
};
int main() {
// Init
vector<int> v({1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
priority_queue<int, vector<int>, cmp<int>> pq(v.begin(), v.end());
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
return 0;
}
Output:
2
4
6
8
10
1
3
5
7
9
To make the demo more clear, I've added some numbers. And for example use vector<int> container to initialize priority_queue<int>.
References
- https://iq.opengenus.org/initialize-priority-queue-in-cpp/
- https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator