（1）queue和priority_queue的區(qū)別
- 普通的隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)盗忱，元素在隊(duì)列尾追加格郁，而從隊(duì)列頭刪除展箱。
- 在優(yōu)先隊(duì)列中旨枯，元素被賦予優(yōu)先級(jí)。當(dāng)訪問元素時(shí)混驰，具有最高優(yōu)先級(jí)的元素最先刪除攀隔。優(yōu)先隊(duì)列具有最高級(jí)先出 （first in, largest out）的行為特征。
（2）實(shí)現(xiàn)
優(yōu)先隊(duì)列具有隊(duì)列的所有特性栖榨，包括隊(duì)列的基本操作昆汹，只是在這基礎(chǔ)上添加了內(nèi)部的一個(gè)排序，它本質(zhì)是一個(gè)堆實(shí)現(xiàn)的婴栽。
<1>定義
priority_queue< type, container, function >
- Type 就是數(shù)據(jù)類型满粗，
- Container 就是容器類型（Container必須是用數(shù)組實(shí)現(xiàn)的容器，比如vector,deque等等愚争，但不能用 list映皆。STL里面默認(rèn)用的是vector），
- Functional 就是比較的方式轰枝。
當(dāng)需要用自定義的數(shù)據(jù)類型時(shí)才需要傳入這三個(gè)參數(shù)捅彻，使用基本數(shù)據(jù)類型時(shí)，只需要傳入數(shù)據(jù)類型鞍陨，默認(rèn)是大頂堆步淹。
<2>大頂堆和的小頂堆
//升序隊(duì)列，小頂堆(因?yàn)槭窍冗M(jìn)先出的诚撵，greater就是“>”)
priority_queue <int,vector<int>,greater<int> > q;
//降序隊(duì)列缭裆，大頂堆
priority_queue <int,vector<int>,less<int> >q;
//這里一定要有空格，不然成了右移運(yùn)算符
greater和less是std實(shí)現(xiàn)的兩個(gè)仿函數(shù)（就是使一個(gè)類的使用看上去像一個(gè)函數(shù)寿烟。其實(shí)現(xiàn)就是類中實(shí)現(xiàn)一個(gè)operator()澈驼，這個(gè)類就有了類似函數(shù)的行為，就是一個(gè)仿函數(shù)類了）
less<int>和greater<int>韧衣，需要頭文件：#include <functional>
（3）實(shí)例
<1>基本類型優(yōu)先隊(duì)列
//對(duì)于基礎(chǔ)類型 默認(rèn)是大頂堆
priority_queue<int> a;//等同于 priority_queue<int, vector<int>, less<int> > a;
//小頂堆
priority_queue<int, vector<int>, greater<int> > b;
for(int i=0;i<5;++i){
a.push(i);
b.push(i);
}
while (!a.empty()){
cout << a.top() << ' ';
a.pop();
}
cout << endl;
while (!c.empty()){
cout << c.top() << ' ';
c.pop();
}
- 運(yùn)行結(jié)果：
4 3 2 1 0（大頂堆）
0 1 2 3 4（小頂堆）
<2>用pair做優(yōu)先隊(duì)列元素
規(guī)則：pair的比較盅藻，先比較第一個(gè)元素，第一個(gè)相等比較第二個(gè)畅铭。
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty())
{
cout << a.top().first << ' ' << a.top().second << '\n';
a.pop();
}
- 運(yùn)行結(jié)果
2 3
1 5
1 2
<3>自定義類型做優(yōu)先隊(duì)列元素
//方法1
struct tmp1 //運(yùn)算符重載<
{
int x;
tmp1(int a) {x = a;}
bool operator<(const tmp1& a) const {
return x < a.x; //大頂堆
}
};
//方法2
struct tmp2 //重寫仿函數(shù)
{
bool operator() (tmp1 a, tmp1 b){
return a.x < b.x; //大頂堆
}
};
int main(){
tmp1 a(1);
tmp1 b(2);
tmp1 c(3);
priority_queue<tmp1> d;
d.push(b);
d.push(c);
d.push(a);
while (!d.empty()){
cout << d.top().x << '\n';
d.pop();
}
cout << endl;
priority_queue<tmp1, vector<tmp1>, tmp2> f;
f.push(b);
f.push(c);
f.push(a);
while (!f.empty()){
cout << f.top().x << '\n';
f.pop();
}
}
- 運(yùn)行結(jié)果
3 2 1
3 2 1
