C++ STL priority_queue 使用说明

说明

优先队列std::priority_queue 可用于构造堆。

比如：
大顶堆：priority_queue<int> q;，大的数在前边。
小顶堆： priority_queue<int, vector<int>, greater<int> > q;，小的数在前边。

std::priority_queue是个模板类，如下：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

有3个模板参数，其中后两个都有默认值。第1个参数是数据类型，比如int。第2个参数是用于存储元素的底层容器类型，默认是用vector。第3个参数是比较函数，默认是less，所以默认是大顶堆，大的在前边。

第2个容器参数，vector和deque满足使用要求，如果是要自己编写的容器代码，则要求自己写的容器代码能最忌访问，且有如下接口：empty(); size(); front(); push_back(); pop_back()。日常使用，使用vector即可。

头文件

#include <queue>

基本操作

操作	说明
top	访问栈顶元素
empty	检查底层的容器是否为空
size	返回容纳的元素数
push	插入元素，并对底层容器排序
pop	删除栈顶元素
swap	两个priority queue交换内容
emplace（c++11引入）	原位构造元素并排序底层容器

其中emplace由c++11引入，功能与push一致，但是效率更高，原地构造，不涉及copy和move操作。

例子：大顶堆

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> pq;
    pq.push(30);
    pq.push(100);
    pq.push(25);
    pq.push(40);

    // output
    while (!pq.empty()) {
        cout << pq.top() << "\t";
        pq.pop();
    }
    cout << endl;

    return 0;
}

结果如下：

100     40      30      25

例子：小顶堆

#include <iostream>
#include <queue>
#include <functional>

using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int> > pq;
    pq.push(30);
    pq.push(100);
    pq.push(25);
    pq.push(40);

    // output
    while (!pq.empty()) {
        cout << pq.top() << "\t";
        pq.pop();
    }
    cout << endl;

    return 0;
}

结果如下：

25      30      40      100

例子：自定义排序函数

#include <iostream>
#include <queue>

using namespace std;

class A {
public:
    A(int key1, int key2) : key1_(key1), key2_(key2) {}

    bool operator<(const A& other) const {
        return (key2_ < (other.key2_));
    }

    void print() const {
        cout << key1_ << "\t" << key2_ << endl;
    }

private:
    int key1_;
    int key2_;
};

int main()
{
    priority_queue<A> pq;
    pq.emplace(25, 26);
    pq.emplace(100, 7);
    pq.emplace(30, 63);
    pq.emplace(40, 6);

    // output
    while (!pq.empty()) {
        pq.top().print();
        pq.pop();
    }
    cout << endl;

    return 0;
}

结果如下：

30      63
25      26
100     7
40      6

通过operator<自定义排序函数，按照key2_从大到小排序。
其中使用了emplace，也可换成pq.push(A(25, 26));。

参考

http://www.cplusplus.com/reference/queue/priority_queue/
https://zh.cppreference.com/w/cpp/container/priority_queue