【概述】

priority_queue（優(yōu)先隊(duì)列）是定義在 <queue> 頭文件中的一個(gè)模板類，其底層是用堆來(lái)實(shí)現(xiàn)的。

與 queue（隊(duì)列）相比，優(yōu)先隊(duì)列不是按照入隊(duì)順序出隊(duì)，而是按照隊(duì)列中元素的優(yōu)先權(quán)出隊(duì)。默認(rèn)情況下，按照大者優(yōu)先的順序出隊(duì)，也可以指定算子來(lái)指定所需的優(yōu)先順序。

關(guān)于堆：點(diǎn)擊這里

【定義】

定義：?priority_queue<elemType, conType, greater/less> priority_queueName

參數(shù)：第一個(gè)是元素類型，第二個(gè)是容器類型，第三個(gè)是比較算子，后兩個(gè)均可省略，默認(rèn)容器為 vector，默認(rèn)算子為 less（小的向前排，大的向后排，出隊(duì)時(shí)序列尾元素先出隊(duì)）

priority_queue<int> q1; //定義數(shù)據(jù)類型為int，默認(rèn)大的先出隊(duì) priority_queue< pair<int,int> > q2; //定義數(shù)據(jù)類型為pair，默認(rèn)大的先出隊(duì) priority_queue<int, vector<int>, greater<int> > q3; //定義小的先出隊(duì)

【比較算子的定義】

如果要定義自己的比較算子，方法有很多種，最常見(jiàn)的一種是：重載比較運(yùn)算符。

將兩個(gè)元素 x 和 y 代入比較運(yùn)算符 (對(duì) less 算子，調(diào)用 x<y，對(duì) greater 算子，調(diào)用 x>y)，若結(jié)果為真，則 x 排在 y 前面，y 將先于 x 出隊(duì)，反之，則將 y 排在 x 前面，x 將先出隊(duì)。

例如：

1）按照 z 的順序從大到小出隊(duì)：

/*運(yùn)行結(jié)果：3 3 62 2 51 5 44 4 3 */ #include<iostream> #include<queue> using namespace std; struct T{int x,y,z;T(int a, int b, int c):x(a), y(b), z(c){}bool operator < (const T &t1, const T &t2) const {return t1.z<t2.z; //按照z的順序來(lái)決定t1和t2的順序} }; int main(){priority_queue<T> q;q.push(T(4,4,3));q.push(T(2,2,5));q.push(T(1,5,4));q.push(T(3,3,6));while (!q.empty()){T t=q.top();q.pop();cout<<t.x<<" "<<t.y<<" "<<t.z<<endl;}return 0; }

2）按照 z 的順序從小到大出隊(duì)

/*運(yùn)行結(jié)果：4 4 31 5 42 2 53 3 6 */ #include<iostream> #include<queue> using namespace std; struct T{int x,y,z;T(int a, int b, int c):x(a), y(b), z(c){}bool operator > (const T &t1, const T &t2) const {return t1.z>t2.z; //按照z的順序來(lái)決定t1和t2的順序} }; int main(){priority_queue< T,vector<T>,greater<T> > q;q.push(T(4,4,3));q.push(T(2,2,5));q.push(T(1,5,4));q.push(T(3,3,6));while (!q.empty()){T t=q.top();q.pop();cout<<t.x<<" "<<t.y<<" "<<t.z<<endl;}return 0; }

【基本操作】

priority_queue 的基本操作與 queue 相同：

• q.push(x)：入隊(duì)，將 x 存入隊(duì)列末端
• q.pop()：出隊(duì)，將隊(duì)列的第一個(gè)元素彈出
• q.front()：訪問(wèn)隊(duì)首元素
• q.back()：訪問(wèn)隊(duì)尾元素
• q.empty()：判斷隊(duì)列是否為空，當(dāng)隊(duì)列為空時(shí)返回 true，否則返回 false
• q.size()：訪問(wèn)隊(duì)列中元素的個(gè)數(shù)

【例題】

• 合并果子（信息學(xué)奧賽一本通-T1369）：點(diǎn)擊這里
• 看病（信息學(xué)奧賽一本通-T1371）：點(diǎn)擊這里
• 魚(yú)塘釣魚(yú)（信息學(xué)奧賽一本通-T1373）：點(diǎn)擊這里
• Reorder the Array（CF-1008C）：點(diǎn)擊這里
• Fence Repair（POJ-3253）：點(diǎn)擊這里
• 活動(dòng)安排問(wèn)題（51Nod-1428）：點(diǎn)擊這里
• Stall Reservations（POJ-3190）：點(diǎn)擊這里
• Supermarket（POJ-1456）：點(diǎn)擊這里
• 玩具（BZOJ-1307）(queue+priority_queue)：點(diǎn)擊這里
• 3N Numbers（AtCoder-2566）(兩次 priority_queue)：點(diǎn)擊這里
• The Average（POJ-2833）(兩次 priority_queue)：點(diǎn)擊這里

總結(jié)

以上是生活随笔為你收集整理的树形结构 —— 优先队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。