使用C++的优先队列时自定义比较函数

在C++中，优先队列是一种底层使用堆实现的数据结构，位于队首的元素总是目前所有元素中最优的；

所在头文件：#include <queue>

定义方式：priority_queue<Type, Container, Functional> 而C++也提供了两种简单的比较方式，即大顶堆小顶堆

// 小顶堆
priority_queue<int, vector<int>, greater<int> >greaterQue;
// 大顶堆
priority_queue<int, vector<int>, less<int> >lessQue;
greaterQue.push(1);
greaterQue.push(5);
greaterQue.push(2);
lessQue.push(1);
lessQue.push(5);
lessQue.push(2);
// lessQue  = [5, 1, 2]
// greaterQue = [1, 5, 2]

当我们的队列元素不是普通数据类型的时候，我们的比较方式有可能很复杂，我们需要自行定义比较函数，例如当我们需要对结构体进行维护优先队列的时候，一般有两种方法：

• 在结构体中重载运算符
• 结构体外部定义方法，使用该方法进行构造队列

例如，我有一个学生结构体，想要构建一个队首的学生是年龄最小的，当年龄都相同的时候，名字按照字典顺序小的排在前面：

法一：

struct Stu{
    int age;
    string name;
    Stu(int age1, string name1){
        age = age1;
        name = name1;
    }
    bool operator > (const Stu &s1) const {
        if (s1.age == age)return name > s1.name;
        return age > s1.age;
    }
};

int main(){
    ios::sync_with_stdio(false);
    priority_queue<Stu, vector<Stu>, greater<Stu> >que1;
    que1.push(Stu{11, "yalexin"});
    que1.push(Stu{11, "axin"});
    que1.push(Stu{12, "aaaaa"});
    que1.push(Stu{12, "bbbbb"});
    while(!que1.empty()){
        Stu top = que1.top();
        cout << "age ： " << top.age << ", name : " << top.name << endl;
        que1.pop(); 
    }
    return 0;
}

对于上面的代码，控制台输出：

age ： 11, name : axin
age ： 11, name : yalexin
age ： 12, name : aaaaa
age ： 12, name : bbbbb

注意当你打算使用

priority_queue<Stu, vector<Stu>, greater<Stu> >que1

的时候，结构体中需要重载的运算符是>，相应的，你打算使用

priority_queue<Stu, vector<Stu>, greater<Stu> >que1

的时候，你的结构体中就应该重载<

法二：

struct Stu{
    int age;
    string name;
    Stu(int age1, string name1){
        age = age1;
        name = name1;
    }
};
struct MyCmp{
    bool operator()(const Stu &a, const Stu &b){
        if (a.age == b.age) return a.name > b.name;
        return a.age > b.age;
    } 
};
int main(){
    ios::sync_with_stdio(false);
    priority_queue<Stu, vector<Stu>, MyCmp >que1;
    que1.push(Stu{11, "yalexin"});
    que1.push(Stu{11, "axin"});
    que1.push(Stu{12, "aaaaa"});
    que1.push(Stu{12, "bbbbb"});
    while(!que1.empty()){
        Stu top = que1.top();
        cout << "age ： " << top.age << ", name : " << top.name << endl;
        que1.pop(); 
    }
    return 0;
}

两种方法的结果都一样。