- priority_queue:優先隊列,資料預設由大到小排序,即優先權高的資料會先被取出。
- 宣告:
- 把元素 x 加進 priority_queue:
- 讀取優先權最高的值:
- x = pq.top();
- pq.pop(); // 讀取後刪除
- 判斷是否為空的priority_queue:
- pq.empty() 回傳true
- pq.size() 回傳零
- 如需改變priority_queue的優先權定義:
- priority_queue<T> pq; 預設由大排到小
- priority_queue<T, vector<T>, greater<T> > pq; 改成由小排到大
- priority_queue<T, vector<T>, cmp> pq; 自行定義 cmp 排序
- 自行定義 cmp,使用 struct:
- 注意:因為優先判定為 !cmp,所以「由大排到小」需「反向」定義實現「最小值優先」。反之亦然。
- 【範例】ZeroJudge c875: 107北二2.裝置藝術 【題解】
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
int main(){
priority_queue <pii> pq;
pq.push({4, 5});
pq.push({5, 3});
pq.push({4, 8});
pq.push({2, 7});
pq.push({3, 2});
while (!pq.empty()){
auto now = pq.top();
pq.pop();
cout << now.F << " " << now.S << endl;
}
}
Output:
5 3
4 8
4 5
3 2
2 7
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
int main(){
priority_queue <pii, vector<pii>, greater<pii> > pq;
pq.push({4, 5});
pq.push({5, 3});
pq.push({4, 8});
pq.push({2, 7});
pq.push({3, 2});
while (!pq.empty()){
auto now = pq.top();
pq.pop();
cout << now.F << " " << now.S << endl;
}
}
Output:
2 7
3 2
4 5
4 8
5 3
struct node {
int x, y;
int sq;
node(int _x = 0, int _y = 0) {
//constructor
x = _x;
y = _y;
sq = _x * _x + _y * _y;
}
};
struct cmp {
bool operator()(node a, node b) {
/*
The function call operator () can be overloaded for objects
of class type. When you overload ( ), you are not creating
a new way to call a function.
Rather, you are creating an operator function that can be
passed an arbitrary number of parameters.
priority_queue優先判定為!cmp,所以「由大排到小」需「反向」定義
實現「最小值優先」
*/
return a.x < b.x;
}
};
int main(){
priority_queue <node, vector<node>, cmp> pq;
}
Post Views (since April 2021) : 17,907