優(yōu)先隊(duì)列(priority queue)
普通的隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)墓怀，元素在隊(duì)列尾追加弹囚，而從隊(duì)列頭刪除。在優(yōu)先隊(duì)列中秒啦，元素被賦予優(yōu)先級(jí)熬粗。當(dāng)訪問(wèn)元素時(shí)，具有最高優(yōu)先級(jí)的元素最先刪除余境。優(yōu)先隊(duì)列具有最高級(jí)先出 （largest-in驻呐，first-out）的行為特征。
STL中的優(yōu)先隊(duì)列-priorit_queue芳来，包含在頭文件”queue”中含末，可以使用具有默認(rèn)優(yōu)先級(jí)的已有數(shù)據(jù)結(jié)構(gòu)；也可以再定義優(yōu)先隊(duì)列的時(shí)候傳入自定義的優(yōu)先級(jí)比較對(duì)象即舌；或者使用自定義對(duì)象(數(shù)據(jù)結(jié)構(gòu))佣盒，但是必須重載好< 操作符。
1顽聂、優(yōu)先隊(duì)列的常用操作
q.empty() 如果隊(duì)列為空肥惭，則返回true，否則返回false
q.size() 返回隊(duì)列中元素的個(gè)數(shù)
q.pop() 刪除隊(duì)首元素紊搪，但不返回其值
q.top() 返回具有最高優(yōu)先級(jí)的元素值蜜葱，但不刪除該元素
q.push(item) 在基于優(yōu)先級(jí)的適當(dāng)位置插入新元素
其中q.top()為查找操作，在最小優(yōu)先隊(duì)列中搜索優(yōu)先權(quán)最小的元素耀石，在最大優(yōu)先隊(duì)列中搜索優(yōu)先權(quán)最大的元素牵囤。q.pop()為刪除該元素。優(yōu)先隊(duì)列插入和刪除元素的復(fù)雜度都是O(lgn)滞伟，所以速度很快揭鳞；另外，在優(yōu)先隊(duì)列中诗良，元素可以具有相同的優(yōu)先權(quán)汹桦。
priority_queue模板原型
priority_queue模板原型
template< class T ,class Sequence=vector<T> ,classCompare=less<typenameSequence::value_type> >class priority_queue;
2.優(yōu)先隊(duì)列常用定義和重載運(yùn)算符方法
1）、默認(rèn)優(yōu)先級(jí)
#include <queue>
using namespace std;
priority_queue<int> q;
通過(guò)<操作符可知在整數(shù)中元素大的優(yōu)先級(jí)高鉴裹。
2）、傳入一個(gè)比較函數(shù)，使用functional.h函數(shù)對(duì)象作為比較函數(shù)径荔。
#include <queue>
#include <functional>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q;
此時(shí)整數(shù)中元素小的優(yōu)先級(jí)高督禽。
3）、傳入比較結(jié)構(gòu)體总处，自定義優(yōu)先級(jí)
#include <queue>
using namespace std;
struct cmp{
bool operator ()(int a,int b){ //通過(guò)傳入不同類(lèi)型來(lái)定義不同類(lèi)型優(yōu)先級(jí)
return a>b; //最小值優(yōu)先
}
};
/**
struct cmp{
bool operator ()(int a,int b){
return a<b; //最大值優(yōu)先
}
};
**/
priority_queue<int, vector<int>, cmp > q;
4）狈惫、自定義數(shù)據(jù)結(jié)構(gòu)，自定義優(yōu)先級(jí)
#include <queue>
using namespace std;
struct node {
int priority;
int value;
friend bool operator < (const node &a, const node &b) {
return a.priority < b.priority;
}
/* 這樣寫(xiě)也可以
bool operator < (const node &a) const {
return priority < a.priority;
}
*/
};
/**
因?yàn)闃?biāo)準(zhǔn)庫(kù)默認(rèn)使用元素類(lèi)型的<操作符來(lái)確定它們之間的優(yōu)先級(jí)關(guān)系鹦马。而且自定義類(lèi)型的<操作符與>操作符并無(wú)直接聯(lián)系胧谈，故會(huì)編譯不過(guò)。
struct node {
int priority;
int value;
friend bool operator > (const node &a, const node &b) { //錯(cuò)誤示范
return a.priority > b.priority;
}
};
**/
priority_queue<node> q;
