priority_queue 調用 STL里面的 make_heap(), pop_heap(), push_heap() 算法
實現，也算是堆的另外一種形式。

先寫一個用 STL 里面堆算法實現的與真正的STL里面的 priority_queue? 用法相
似的 priority_queue， 以加深對 priority_queue 的理解

#include?<iostream>
#include?<algorithm>
#include?<vector>

using?namespace?std;

class?priority_queue
{
????private:
????????vector<int>?data;
????????
????public:
????????void?push(?int?t?){?
????????????data.push_back(t);?
????????????push_heap(?data.begin(),?data.end());?
????????}
????????
????????void?pop(){
????????????pop_heap(?data.begin(),?data.end()?);
????????????data.pop_back();
????????}
????????
????????int?top()????{?return?data.front();?}
????????int?size()???{?return?data.size();??}
????????bool?empty()?{?return?data.empty();?}
};


int?main()
{
????priority_queue??test;
????test.push(?3?);
????test.push(?5?);
????test.push(?2?);
????test.push(?4?);
????
????while(?!test.empty()?){
????????cout?<<?test.top()?<<?endl;
????????test.pop();?}
????????
????return?0;
}

STL里面的 priority_queue 寫法與此相似，只是增加了模板及相關的迭代器什么的。

priority_queue 對于基本類型的使用方法相對簡單。
他的模板聲明帶有三個參數，priority_queue<Type, Container, Functional>
Type 為數據類型， Container 為保存數據的容器，Functional 為元素比較方式。
Container 必須是用數組實現的容器，比如 vector, deque 但不能用 list.
STL里面默認用的是 vector. 比較方式默認用 operator< , 所以如果你把后面倆個
參數缺省的話，優先隊列就是大頂堆，隊頭元素最大。
看例子

#include?<iostream>
#include?<queue>

using?namespace?std;

int?main(){
????priority_queue<int>?q;
????
????for(?int?i=?0;?i<?10;?++i?)?q.push(?rand()?);
????while(?!q.empty()?){
????????cout?<<?q.top()?<<?endl;
????????q.pop();
????}
????
????getchar();
????return?0;
}

如果要用到小頂堆，則一般要把模板的三個參數都帶進去。
STL里面定義了一個仿函數 greater<>，對于基本類型可以用這個仿函數聲明小頂堆
例子:

#include?<iostream>
#include?<queue>

using?namespace?std;

int?main(){
????priority_queue<int,?vector<int>,?greater<int>?>?q;
????
????for(?int?i=?0;?i<?10;?++i?)?q.push(?rand()?);
????while(?!q.empty()?){
????????cout?<<?q.top()?<<?endl;
????????q.pop();
????}
????
????getchar();
????return?0;
}

?對于自定義類型，則必須自己重載 operator< 或者自己寫仿函數
先看看例子:

#include?<iostream>
#include?<queue>

using?namespace?std;

struct?Node{
????int?x,?y;
????Node(?int?a=?0,?int?b=?0?):
????????x(a),?y(b)?{}
};

bool?operator<(?Node?a,?Node?b?){
????if(?a.x==?b.x?)?return?a.y>?b.y;
????return?a.x>?b.x;?
}

int?main(){
????priority_queue<Node>?q;
????
????for(?int?i=?0;?i<?10;?++i?)
????q.push(?Node(?rand(),?rand()?)?);
????
????while(?!q.empty()?){
????????cout?<<?q.top().x?<<?'?'?<<?q.top().y?<<?endl;
????????q.pop();
????}
????
????getchar();
????return?0;
}

自定義類型重載 operator< 后，聲明對象時就可以只帶一個模板參數。
但此時不能像基本類型這樣聲明
priority_queue<Node, vector<Node>, greater<Node> >;
原因是 greater<Node> 沒有定義，如果想用這種方法定義
則可以按如下方式

例子:

#include?<iostream>
#include?<queue>

using?namespace?std;

struct?Node{
????int?x,?y;
????Node(?int?a=?0,?int?b=?0?):
????????x(a),?y(b)?{}
};

struct?cmp{
????bool?operator()?(?Node?a,?Node?b?){
????????if(?a.x==?b.x?)?return?a.y>?b.y;
????????
????????return?a.x>?b.x;?}
};

int?main(){
????priority_queue<Node,?vector<Node>,?cmp>?q;
????
????for(?int?i=?0;?i<?10;?++i?)
????q.push(?Node(?rand(),?rand()?)?);
????
????while(?!q.empty()?){
????????cout?<<?q.top().x?<<?'?'?<<?q.top().y?<<?endl;
????????q.pop();
????}
????
????getchar();
????return?0;
}

priority_queue

在優先隊列中，優先級高的元素先出隊列。
標準庫默認使用元素類型的<操作符來確定它們之間的優先級關系。
優先隊列的第一種用法，也是最常用的用法：

priority_queue<int>?qi;

通過<操作符可知在整數中元素大的優先級高。
故示例1中輸出結果為：9 6 5 3 2

第二種方法：
在示例1中，如果我們要把元素從小到大輸出怎么辦呢？
這時我們可以傳入一個比較函數，使用functional.h函數對象作為比較函數。

priority_queue<int,?vector<int>,?greater<int>?>qi2;

其中
第二個參數為容器類型。
第二個參數為比較函數。
故示例2中輸出結果為：2 3 5 6 9

第三種方法：
自定義優先級。

struct?node
{
????friend?bool?operator<?(node?n1,?node?n2)
????{
????????return?n1.priority?<?n2.priority;
????}
????int?priority;
????int?value;
};

在該結構中，value為值，priority為優先級。
通過自定義operator<操作符來比較元素中的優先級。
在示例3中輸出結果為：
優先級? 值
9?????? ???5
8????????? 2
6??????????1
2??????????3
1??????????4
但如果結構定義如下：

struct?node
{
????friend?bool?operator>?(node?n1,?node?n2)
????{
????????return?n1.priority?>?n2.priority;
????}
????int?priority;
????int?value;
};

則會編譯不過（G++編譯器）
因為標準庫默認使用元素類型的<操作符來確定它們之間的優先級關系。
而且自定義類型的<操作符與>操作符并無直接聯系，故會編譯不過。

//代碼清單

?

#include<iostream>
#include<functional>
#include<queue>
using?namespace?std;
struct?node
{
????friend?bool?operator<?(node?n1,?node?n2)
????{
????????return?n1.priority?<?n2.priority;
????}
????int?priority;
????int?value;
};
int?main()
{
????const?int?len?=?5;
????int?i;
????int?a[len]?=?{3,5,9,6,2};
????//示例1
????priority_queue<int>?qi;
????for(i?=?0;?i?<?len;?i++)
????????qi.push(a[i]);
????for(i?=?0;?i?<?len;?i++)
????{
????????cout<<qi.top()<<"?";
????????qi.pop();
????}
????cout<<endl;
????//示例2
????priority_queue<int,?vector<int>,?greater<int>?>qi2;
????for(i?=?0;?i?<?len;?i++)
????????qi2.push(a[i]);
????for(i?=?0;?i?<?len;?i++)
????{
????????cout<<qi2.top()<<"?";
????????qi2.pop();
????}
????cout<<endl;
????//示例3
????priority_queue<node>?qn;
????node?b[len];
????b[0].priority?=?6;?b[0].value?=?1;?
????b[1].priority?=?9;?b[1].value?=?5;?
????b[2].priority?=?2;?b[2].value?=?3;?
????b[3].priority?=?8;?b[3].value?=?2;?
????b[4].priority?=?1;?b[4].value?=?4;?

????for(i?=?0;?i?<?len;?i++)
????????qn.push(b[i]);
????cout<<"優先級"<<'\t'<<"值"<<endl;
????for(i?=?0;?i?<?len;?i++)
????{
????????cout<<qn.top().priority<<'\t'<<qn.top().value<<endl;
????????qn.pop();
????}
????return?0;
}

總結

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

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