STL--priority queue的使用

简介：

　　优先队列是一种容器适配器，优先队列的第一个元素总是最大或最小的（自定义的数据类型需要重载运算符）。它是以堆为基础实现的一种数据结构。

成员函数(Member functions)

(constructor): Construct priority queue (public member function)
empty: Test whether container is empty (public member function)
size: Return size (public member function)
top: Access top element (public member function)
push: Insert element (public member function)
pop: Remove top element (public member function)

代码示例

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<functional>
#include<queue>
#include<vector>

using namespace std;
int arr[] = {1, 9, 2, 8, 3, 7, 4, 5, 3, 5, 10, 8, 9};

struct node
{
    friend bool operator < (node n1, node n2)
    {
        return n1.index < n2.index;
    }
    friend bool operator > (node n1, node n2)
    {
        return n1.index > n2.index;
    }

    int index;
    int value;
};

node b[]= {{10,100},
    {99,50000},
    {23,33},
    {44,132},
    {66,44}
};

int main()
{
    //1.常见用法，默认最大元素优先
    priority_queue<int> pq1;
    for(int i = 0 ; i < sizeof(arr) / sizeof(int); i++)
        pq1.push(arr[i]);
    for(int i = 0 ; i < sizeof(arr) / sizeof(int); i++)
    {
        cout<<pq1.top()<<' ';
        pq1.pop();
    }
    cout<<endl;

    //2.注意优先队列的申明方式
    priority_queue<int,vector<int>, greater<int> > pq2;
    for(int i = 0 ; i < sizeof(arr) / sizeof(int); i++)
        pq2.push(arr[i]);
    for(int i = 0 ; i < sizeof(arr) / sizeof(int); i++)
    {
        cout<<pq2.top()<<' ';
        pq2.pop();
    }
    cout<<endl;

    //3.使用自定义的数据类型
    priority_queue<node> pq3;
    for(int i = 0; i < sizeof(b) / sizeof(node); i++)
        pq3.push(b[i]);
    for(int i = 0; i < sizeof(b) / sizeof(node); i++)
    {
        cout<<pq3.top().index<<' '<<pq3.top().value<<endl;
        pq3.pop();
    }
    cout<<endl;
    //4.
    priority_queue<node, vector<node>, greater<node> > pq4;
    for(int i = 0; i < sizeof(b) / sizeof(node); i++)
        pq4.push(b[i]);
    for(int i = 0; i < sizeof(b) / sizeof(node); i++)
    {
        cout<<pq4.top().index<<' '<<pq4.top().value<<endl;
        pq4.pop();
    }

    return 0;
}