要么改变世界,要么适应世界

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

2021-04-10 13:24:25
110
目录

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;
}

两种方法的结果都一样。

历史评论
开始评论