标準模闆庫(STL)學習指南之priority_queue優先隊列

priority_queue 調用 STL裡面的 make_heap(), pop_heap(), push_heap() 算法

實作，也算是堆的另外一種形式。

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

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

<a href="http://blog.csdn.net/suwei19870312/article/details/5294016">view plain</a>

#include &lt;iostream&gt;  

#include &lt;algorithm&gt;  

#include &lt;vector&gt;  

using namespace std;  

class priority_queue  

{  

    private:  

        vector&lt;int&gt; 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 &lt;&lt; test.top() &lt;&lt; endl;  

        test.pop(); }  

    return 0;  

}  

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

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

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

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

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

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

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

看例子

#include &lt;queue&gt;  

int main(){  

    priority_queue&lt;int&gt; q;  

    for( int i= 0; i&lt; 10; ++i ) q.push( rand() );  

    while( !q.empty() ){  

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

        q.pop();  

    }  

    getchar();  

如果要用到小頂堆，則一般要把模闆的三個參數都帶進去。

STL裡面定義了一個仿函數 greater&lt;&gt;，對于基本類型可以用這個仿函數聲明小頂堆

例子:

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

對于自定義類型，則必須自己重載 operator&lt; 或者自己寫仿函數

先看看例子:

struct Node{  

    int x, y;  

    Node( int a= 0, int b= 0 ):  

        x(a), y(b) {}  

bool operator&lt;( Node a, Node b ){  

    if( a.x== b.x ) return a.y&gt; b.y;  

    return a.x&gt; b.x;   

    priority_queue&lt;Node&gt; q;  

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

    q.push( Node( rand(), rand() ) );  

        cout &lt;&lt; q.top().x &lt;&lt; ' ' &lt;&lt; q.top().y &lt;&lt; endl;  

自定義類型重載 operator&lt; 後，聲明對象時就可以隻帶一個模闆參數。

但此時不能像基本類型這樣聲明

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

原因是 greater&lt;Node&gt; 沒有定義，如果想用這種方法定義

則可以按如下方式

struct cmp{  

    bool operator() ( Node a, Node b ){  

        if( a.x== b.x ) return a.y&gt; b.y;  

        return a.x&gt; b.x; }  

    priority_queue&lt;Node, vector&lt;Node&gt;, cmp&gt; q;  

}