優先隊列的使用方式

性質

如同它的名稱，是一個帶有優先順序的隊列，常簡稱為 pq ，可以解決重要任務先做、從所有候選答案中選出最小的等問題，在競賽中特別有用，區間類型的問題也可以用。每次插入東西時需要保證插在正確的位置上，才能在拿東西時快速的拿到，而 STL 中就提供了 priority queue 這樣一個結構，可以在 $O(1)$ 取得現在優先度最高的元素， $O(\log n)$ 刪除優先度最高的元素， $O(\log n)$ 新增元素。 (其實還有 $O(1)$ 取得現在整個 pq 的大小，不過不是很常用到。)

實作

C++ 中並沒有規定用甚麼方式實作，但通常會使用 heap 這個資料結構，由於 heap 在大部分情況下都可以使用 STL 的 set 等內建資料結構替代，相關的內容只需在本教材的樹狀結構和分治中概念上理解即可。

在 C++ 中的使用方式

pq 是少數沒有獨立標頭檔的資料結構，放在 <queue.h> 之中，整個結構中只保證 pq.top() 有意義，因此也沒有迭代器。和 STL 中的其他容器一樣，以模板的方式實現泛型。默認是越大的東西放在越前面，可以在一開始加上參數設定比較方法，尖括號中第一個參數代表要儲存的資料型態，第二和三個是可選的，第二個是一個可以隨機訪問的容器，用來實作 pq ，第三個是比較的函式，但是因為 template 本身需要傳入一個型態當作參數，而不能直接傳入一個函式，常見的實現方式是 function object ，透過宣告一個 struct ，並重載 () 運算子，讓他能以 cmp(a,b) 的形式被使用，而 <functional> 中有現成的模板可以使用，省去了自己寫的麻煩(不過要特別背就是了)。 (有個競程小技巧，如果有多筆詢問類的題目，可以 pq=priority_queue<T>() 直接得到空的 pq ，原本的 pq 就丟著，直到程式結束才會統一回收，但在專案等地方會有記憶體洩露的問題，使用上要自行斟酌。) (另一個小技巧，如果連 greater<T> 都懶得背，可以把傳入的東西乘以 -1 ，就能得到反轉的效果了。)

#include <iostream>
#include <queue>
#include <functional>
using namespace std;
int main(){
    priority_queue<int>pq;
    for(int e:(const int[]){3,7,2,6,0})pq.push(e);//push可以放入一個元素，會自動排序
    for(;!pq.empty();pq.pop())cout<<pq.top()<<' ';//empty回傳bool，代表是否為空。top可以知道現在最上面的元素是甚麼。pop移除最上面的元素。
    //輸出7 6 3 2 0

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq2;//除了greater，還有greater_equal,less,less_equal可以用
    for(auto e:(const pair<int,int>[]){{1,3},{6,3},{5,7},{5,0}})pq2.push(e);//將一堆二維點對先依first排序，相同再依second排序
    for(;pq2.size();pq2.pop())cout<<"{"<<pq2.top().first<<','<<pq2.top().second<<"} ";//輸出{1,3} {5,0} {5,7} {6,3}
}