优先队列-priority_queue

不出所料，priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理。但是如何定义“优先级”完全取决于我们自己。如果一个优先级队列记录的是医院里等待接受急救的病人，那么病人病情的严重性就是优先级。如果队列元素是银行的借贷业务，那么借记可能会优先于信贷。

定义优先队列

priority_queue 模板有 3 个参数，其中两个有默认的参数；第一个参数是存储对象的类型，第二个参数是存储元素的底层容器，第三个参数是函数对象，它定义了一个用来决定元素顺序的断言。因此模板类型是：

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

如你所见，priority_queue 实例默认有一个 vector 容器。函数对象类型 是一个默认的排序断言，定义在头文件 function 中，决定了容器中最大的元素会排在队列前面。fonction 中定义了 greater<T>，用来作为模板的最后一个参数对元素排序，最小元素会排在队列前面。当然，如果指定模板的最巵一个参数，就必须提供另外的两个模板类型参数。

//升序队列
priority_queue <int, vector<int>,greater<int> > q;
//降序队列
priority_queue <int, vector<int>,less<int> >q;
// greater<int>, less<int> 是 std 中的仿函数

实例

#include <queue>
// 默认是大顶堆
priority_queue<int> a;
// priority_queue<int, vector<int>, less<int> > a;

for(int i = 0; i < 5; i++) {
    a.push(i);
}

while(!a.empty()) {
    cout << a.top() << ' ';
    a.pop();
}
// 4 3 2 1 0

复杂类型的优先队列

typedef pair<int,int> pii;

priority_queue<pii, vector<pii>, greater<pii>> pq;

pg.emplace(1, 1);

更复杂的实例

auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
    return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

pq.emplace(1, 0);

auto [x, y] = pq.top();

vector<vector<int>> ans;

ans.emplace_back(initializer_list<int>{x, y});