priority_queue用法

在優先隊列中，優先級高的元素先出隊列。

先寫一個用 STL 裡面堆算法實作的與真正的STL裡面的 priority_queue 用法相

似的 priority_queue， 以加深對 priority_queue 的了解

push_heap()：将容器中的最後一個元素加入堆中

pop_head()：将堆中最大的(或者自定義比較函數，預設為<)元素推到容器首

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

}  

 運作結果：

<a target="_blank" href="http://blog.51cto.com/attachment/201110/213543420.jpg"></a>

STL裡面的 priority_queue 寫法與此相似，隻是增加了模闆及相關的疊代器什麼的。

priority_queue 對于基本類型的使用方法相對簡單。

他的模闆聲明帶有三個參數，priority_queue&lt;Type, Container, Functional&gt;

Type 為資料類型， Container 為儲存資料的容器，Functional 為元素比較方式。

Container 必須是用數組實作的容器，比如 vector, deque 但不能用 list.

STL裡面預設用的是 vector. 比較方式預設用 operator&lt; , 是以如果你把後面倆個

參數預設的話，優先隊列就是大頂堆，隊頭元素最大。

(1)使用預設參數

#include &lt;queue&gt;  

int main(){  

    priority_queue&lt;int&gt; q;  

    for( int i= 0; i&lt; 10; ++i )  

        q.push(i%4);  

    while( !q.empty() ){  

        cout &lt;&lt; q.top() &lt;&lt; endl;  

        q.pop();  

    }  

} 

(2)自定義比較函數(可以使用STL裡的函數greater&lt;int&gt;等，或者重載&lt;，這樣就不需要用三個參數，或者自定義比較函數)

priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt;;

bool operator&lt;  (int a,int b){return a &lt; b;}

priority_queue&lt;int&gt;

bool cmp(int a,int b) { return a &lt; b;}

priority_queue&lt;int,vector&lt;int&gt;,cmp&gt;;

本文轉自nxlhero 51CTO部落格，原文連結：http://blog.51cto.com/nxlhero/699349，如需轉載請自行聯系原作者