Last Updated on 2022-02-19 by Clay
priority_queue（優先權佇列）是 C++ 標準模板函式庫（Standard Template Library, STL）中所提供的佇列容器，會優先返回優先權最高的元素。
在一般儲存 int 資料的情況下，元素的優先權由大到小排序，當然我們可以自行改變 priority_queue 的優先權定義。
priority_queue 使用方法筆記
以下是一個最簡單的範例程式：
push(): 將元素推入佇列top(): 取出優先權最高的元素pop(): 彈出（刪除）優先權最高的元素
#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
可以看到，我們隨便推入佇列中的元素已經按照由大到小這樣的順序排序了；意味著越大的數值有著越高的優先權。
改變優先權
改成越小的數值的優先權越高
#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
這是最常見的改變之一，我們可以直接使用 greater<int> 來做到。
自定義優先權模式
如果我們希望偶數的優先權比奇數的大、且數字越小優先權越大，那麼我們可以用以下這樣的方法建構自己的優先權規則：
#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
為了讓 demo 的效果比較清楚，我增加了一些數字，順便列出如何使用 vector<int> 容器來初始化 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