優先隊列詳解/C++
優先隊列
1.概念:什么是優先隊列呢?在優先隊列中，元素被賦予優先級，當訪問元素時，具有最高級優先級的元素先被訪問 .即優先隊列具有最高級先出的行為特征。它可以說是隊列和排序的完美結合體，不僅可以存儲數據，還可以將這些數據按照我們設定的規則進行排序。

2.定義:優先隊列在頭文件#include 中；其聲明格式為：priority_queue ans;//聲明一個名為ans的整形的優先隊列

3.支持的操作:

q.empty() //如果隊列為空，則返回true，否則返回false q.size() //返回隊列中元素的個數 q.pop() //刪除隊首元素，但不返回其值 q.top() //返回具有最高優先級的元素值，但不刪除該元素 q.push(item) //在基于優先級的適當位置插入新元素

4實例:

優先隊列的時間復雜度為O（logn），n為隊列中元素的個數，其存取都需要時間。

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

然而更多的情況下，我們是希望可以自定義其優先級的，下面介紹定義優先級的操作

priority_queue 對于基本類型的使用方法相對簡單。他的模板聲明帶有三個參數:

priority_queue<Type, Container, Functional> 其中Type 為數據類型， Container 為保存數據的容器，Functional 為元素比較方式。
Container 必須是用數組實現的容器，比如 vector, deque 但不能用 list.STL里面默認用的是 vector.

1.比較方式默認用 operator< , 所以如果你把后面倆個參數缺省的話，優先隊列就是大頂堆，隊頭元素最大。(也就是默認非升序)
priority_queue q;

#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; }

2.如果要用到小頂堆，則一般要把模板的三個參數都帶進去。
STL里面定義了一個仿函數 greater<>，對于基本類型可以用這個仿函數聲明小頂堆(非降序)
priority_queue<int, vector, greater > q;

#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; }

3.對于自定義類型，則必須自己重載 operator<
priority_queue q;

#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; }

4.自定義cmp
priority_queue<Node, vector, cmp> q;

#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; }

總結

以上是生活随笔為你收集整理的c++——优先队列(priority_queue)的全部內容，希望文章能夠幫你解決所遇到的問題。

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