优先级队列需要包含头文件<queue>，优先级队列的定义如下：

priority_queue<typename, container, functional>

  • typename是数据的类型；

  • container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；

  • functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。

运算重载符

对于这串代码：

bool operator()(vector<int>&a,vector<int>&b){
    return a[0]<b[0]; 
}

  • 若比较函数返回 true：表示第一个参数（a）的优先级 低于 第二个参数（b），因此 b 会被调整到更靠近堆顶的位置（b 上浮）。

  • 若比较函数返回 false：表示第一个参数（a）的优先级 高于 第二个参数（b），因此 a 会留在当前位置或上浮到堆顶。

假设依次插入 [5], [3], [8]：

  1. 插入 [5]，堆顶为 [5]。

  2. 插入 [3]，比较 3 < 5 为 true，5 保持堆顶。

  3. 插入 [8]，比较 8 < 5 为 false，8 上浮到堆顶。

最终堆顶为 [8]，符合大顶堆特性。

自定义比较函数的5种方式

可以使用现成的 less<T>来定义大顶堆 greater<T>来定义小顶堆

从文档出可以看到，传入的可以是 函数指针或者 函数对象（类对操作符()进行了重载，）

参考链接：函数指针和函数对象 参考链接：decltype

方式一：struct重载运算符()（传入函数对象 ）

struct cmp{
   bool operator()(vector<int>&a,vector<int>&b){
       return a[0]>b[0]; 
   }
};
priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆

方式二：class重载运算符()（传入函数对象 ）

class cmp{   
public:
    bool operator()(vector<int>&a,vector<int>&b){
        return a[0]>b[0]; 
    }
};
priority_queue<vector<int>,vector<vector<int>>,cmp> q;//小顶堆

注意：要写在public中

方法三：定义函数（传入函数指针 ）

bool cmp(vector<int>&a,vector<int>&b){
    return a[0]>b[0];
}
priority_queue<vector<int>,vector<vector<int>>,decltype(&cmp)> q(cmp);//小顶堆

需要通过decltype()关键字从而推导指针的类型decltype(&cmp)

注意：如果作为类成员函数，一定要声明static

static bool cmp(vector<int>&a,vector<int>&b){
    return a[0]>b[0];
}

方法四：lambda表达式（传入函数指针 ）

auto cmp=[](vector<int>&a,vector<int>&b)->bool{
            return a[0]>b[0];
        };
​
priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆

方式五：function包装lambda表达式（传入函数指针）

要加入头文件#include<functional>

function<bool(vector<int>&,vector<int>&)> cmp=[](vector<int>&a,vector<int>&b)->bool{
            return a[0]>b[0];
        };
priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> q(cmp);//小顶堆