C++ STL priority_queue如何更改堆顶元素选取规则？

上一节我们提到，在优先队列容器里，堆顶元素不一定是像字面意思一样是权值最”大“的值，就像1大于0一样，通过仿函数，我们能够更改规则，让这个”大“朝着相反的方向出发，实现”0>1"。如果读者还是第一次听过仿函数这个词的话也没关系，它就相当于类重载了函数调用符'()'，把类当函数使就好了。值得注意的是，在更改规则时需要我们指定优先队列的适配容器，否则无法使用仿函数。

下面就让我们通过代码来了解如何更改堆顶元素选取规则。

#include<iostream>
#include<queue>//这里默认包含vector容器和deque容器以及函数对象库<functional>
using namespace std;
/*priority_queue适配器通过仿函数更改堆顶元素选取规则*/ 
/*天然的公共类*/ 
struct cmp
{
bool operator()(const int& a,const int& b)const 
{
return a>b;
}
};
void test() 
{
priority_queue<int,deque<int> ,cmp> pq;//必须指定适配容器！
/*当然，嫌麻烦直接用STL函数对象库！*/
/*priority_queue<int,deque<int> ,greater<int>> pq;*/
    pq.push(1);
    pq.emplace(114514);
    pq.push(0);
    pq.push(78);
    cout << "更改优先队列堆顶元素选取规则，遍历元素后将会是升序排序："; 
while(!pq.empty())
{
cout << pq.top()<< " ";
pq.pop();
}
cout << '\n';
     
     
}
int main() {
    test();
    return 0;
}

编译结果如下：

可以看到，我们通过仿函数或直接调用标准函数对象都能更改堆顶元素选取规则。

总结：实际工作中，我们可能需要更改堆顶元素选取规则，比如迪杰斯特拉最短路径问题，我们总不可能选取距离最远的路走下去，所以我们需要掌握使用仿函数或者标准函数对象来进行堆顶元素选取，满足我们的工作需求。