priority_queue優先隊列，插入進去的元素都會從大到小排好序

PS：在priority_queue<ll, vector<ll>, greater<ll> > pq;中
第一個參數為數據類型，第二個參數為保存數據的容器（默認為vector<int>），第三個參數為元素比較函數（默認為less）。//默認算子為less，即小的往前排，大的往后排（出隊時序列尾的元素出隊）

struct cmp { operator bool ()(int x, int y) { return　x > y; // x小的優先級高 //也可以寫成其他方式，如： return p[x] > p[y];表示p[i]小的優先級高} }; priority_queue<int, vector<int>, cmp>q; //定義方法 //其中，第二個參數為容器類型。第三個參數為比較函數。

優先隊列試圖將兩個元素x和y代入比較運算符(對less算子，調用x<y，對greater算子，調用x>y)，若結果為真，則x排在y前面，y將先于x出隊，反之，則將y排在x前面，x將先出隊。

STL里面默認用的是 vector. 比較方式默認用 operator< , 所以如果你把后面倆個參數缺省的話，優先隊列就是大頂堆，隊頭元素最大。

基本操作：

empty() 如果隊列為空返回真

pop() 刪除隊頂元素

push() 加入一個元素

size() 返回優先隊列中擁有的元素個數

top() 返回優先隊列隊頂元素（隊列中的front()變成了top()）

在默認的優先隊列中，優先級高的先出隊。在默認的int型中先出隊的為較大的數。

例子

UVA136 - Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1500’th ugly number.
Input
There is no input to this program.
Output
Output should consist of a single line as shown below, with ‘’ replaced by the number
computed.
Sample Output
The 1500’th ugly number is <number>

/* 丑數就是所有是2或3或5倍數的數。 用優先隊列從小到大排列丑數 用set集合判斷丑數是否重復 */#include <iostream> #include <vector> #include <queue> #include <set> using namespace std; typedef long long LL; const int coeff[3]={2,3,5}; int main(){/*PS：在priority_queue<ll, vector<ll>, greater<ll> > pq;中第一個參數為數據類型，第二個參數為保存數據的容器（默認為vector<int>），第三個參數為元素比較函數（默認為less）。*/ priority_queue<LL,vector<LL>,greater<LL> > pq;set<LL> s;pq.push(1);s.insert(1);for(int i=1;;i++){//pq存的第一個數的2，3，5倍找出存到set和pq里并刪除pq第一個數,直至第1500個數 LL x=pq.top();pq.pop();if(i==1500){cout<<"The 1500'th ugly number is "<<x<<".\n";break;}for(int j=0;j<3;j++){ LL x2=x*coeff[j];if(!s.count(x2)){s.insert(x2);pq.push(x2);}}}return 0; }

總結

以上是生活随笔為你收集整理的priority_queuey用法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。