时间戳

首页 > 解决方案 > C ++中优先级队列自定义排序中的异常

c++ - C ++中优先级队列自定义排序中的异常

问题描述

我浏览了几篇关于 C++ 中自定义排序优先级队列的 StackOverflow 和 Codeforces 文章。默认情况下，C++ 实现是 MaxHeap ，因此它会以降序输出元素。我的微调添加greater<int>会上升。我使用自己的比较器功能进行了尝试，如下所示：

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
bool operator()(const int &a,const int &b){
        return a>b;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

这给出了预期的输出：1 5 8

但是，如果我将其更改为：

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
bool operator()(const int &a,const int &b){
        if(a>b)
            return true;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

输出变为：8 1 5

我不知何故无法得到这个，非常感谢任何帮助。

标签： c++queuepriority-queueminmax-heap

解决方案

我建议您阅读编译器警告...您会看到bool operator()(const int &a,const int &b)ifa<=b没有返回语句...这是未定义的行为

相反，您应该这样做：

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
    bool operator()(const int &a,const int &b){
        if(a>b)
            return true;
        /* else */ return false;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

推荐阅读