不像棧和隊列,雖然STL有較好實現但是我們自己也可以很方便的實現,優先隊列自己實現起來就比較復雜,比較浪費時間(而且自己目前也不會233)而優先隊列因為其較好的特性經常被使用,因此對它的熟練掌握是做題的基礎。
頭文件#include< queue >
定義方法:
- 普通方法
priority_queue< int ,vector< int> ,greater< int> > q小的優先級比較高,大的后出隊
pritority_queue<int ,vector< int>,less< int > >q大的優先級比較高先出隊,小的后出隊
為方便記憶,最好理解成比較函數是為了確定隊尾元素的優先級
需要注意比較函數右邊> >中間應該用空格隔開,否則會被看成>>出錯
默認情況下,即priority_queue q;是小的先出隊大的后出隊 - 自定義優先級
struct cmp
{bool operator()(int x,int y){return x>y;//x小的優先級高 }
};
protority_queue<int,vector<int>,cmp>;
- 結構體定義
struct node
{int x,y;friend bool operator < (node a,int b){return a.x>b.x; //x小的優先級高 }
};
priority_queue<node>q;
- 其他常用的操作
empty() //如果隊列為空返回為真
pop() //刪除隊頂元素
push() //加入一個元素
size() //返回隊列中元素的個數
top() //返回優先隊列隊頂元素