[置顶] STL之优先队列priority_queue浅析

优先队列是队列的一种，普通队列queue默认是先进先出，而优先队列则是按照自己定义的方式出，其原理是STL中的堆，调用了函数make_heap(),push_heap(),pop_heap()来实现其操作。当我们每次在头文件queue中调用优先队列使用其操作函数push(),pop(), 其都会进行动态调整来达到我们预期目的。

优先队列基本形式priority_queue<type,container,functional>

其中type为数据类型，container为存放数组的容器，比如vector,deque,但不能是list，其中STL中默认是vector.functional是元素比较方式，STL中默认是operator<，当我们在使用时如果默认后面两个参数缺省，那么就是大顶堆，默认优先大的元素先出来。

下面简单来实现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;

}

优先队列常用几个函数（跟queue相似）：

size();优先队列大小

empty();判空

top();队尾元素

push();进队

pop();删除

大顶堆（STL中默认的使用方法，大的元素先出队列）

#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<，第二种是自定义仿函数

1.重载方式（注意使用时还是按照默认参数形式使用）：

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

2.自定义仿函数（按照小顶堆方式使用，但不同的是第三个参数不再是greater<type>,而是自定义比较仿函数）：

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