【筆記】常用C++ STL:priority_queue

  • priority_queue:優先隊列,資料預設由大到小排序,即優先權高的資料會先被取出。
  • 宣告:
    • priority_queue <int> pq;
  • 把元素 x 加進 priority_queue:
    • pq.push(x);
  • 讀取優先權最高的值:
    • 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:
    • Overload operator()
    • 注意:因為優先判定為 !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;
}
分享本文 Share with friends