标准模板库(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;  

}