優先佇列 Priority Queue

實現

• std::priority_queue背後是heap

用途

• 為一序列容器
• 是一個帶優先級的queue
• 可以很快很方便的加入元素或取出當前最優先的元素

用法

宣告

• 需要引入函式庫<queue>

#include <queue>
//priority_queue<"dataType", "container", "comparisonFunction"> "name";
//container默認為vector，comparisonFunction默認為由大到小排序

priority_queue<int> test;
priority_queue<int, vector<int>, greater<int> > pq; //由小到大

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
} //priority_queue優先判定為!cmp，所以這個cmp會使pq中小的優先
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq;

函式

狀態回傳
priority_queue.empty(); //回傳priority_queue是否為空
priority_queue.size(); //回傳priority_queue目前元素數

加入移除元素
priority_queue.push(e); //將e加入priority_queue
priority_queue.pop(); //移除priority_queue中的第一個元素

操作元素
priority_queue.top(); //呼叫priority_queue中的第一個元素

• 插入和移除的複雜度為
  $O(logN)$，初始化的複雜度為
  $O(logN)$(建立heap，若建立後再一個一個push則為
  $O(NlogN)$)
• 呼叫元素的複雜度為
  $O(1)$