C++中使用自定义比较器实现priority_queue降序排列

嘿，我来帮你修正这个C++优先级队列的排序逻辑！你现在的代码是按frequency从小到大排的（小顶堆），要改成从大到小的大顶堆，只需要调整自定义比较类的逻辑就行，下面给你详细说：

问题出在哪？ #

你原来的ComparisonClass里，operator()返回a->frequency - b->frequency，这会让频率小的Node优先级更高——因为C++的priority_queue会把比较器返回true的元素往后放。比如当a的频率比b小的时候，这个减法结果是负数，会被视为true，所以a就被排到b后面，最终队列是小的在前、大的在后，和你要的正好相反。

而且这里还有个小问题：返回int类型来做比较其实不太规范，C++的比较器应该返回bool类型，这样更安全也符合标准。

修正方案（推荐第一种） #

方法1：用bool比较反转优先级（最规范） #

把比较器改成判断a的频率是否小于b，这样频率大的Node会被优先放在队首。代码如下：

class Node { 
public: 
    char character; 
    int frequency; 
    Node *left, *right; 
}; 

class ComparisonClass { 
public: 
    // 核心修改：返回bool，当a的频率小于b时，a优先级更低，排后面
    bool operator()(Node *a, Node *b) { 
        return a->frequency < b->frequency; 
    } 
}; 

priority_queue<Node*, vector<Node*>, ComparisonClass> queue;

方法2：调整减法顺序（不推荐，有溢出风险） #

如果你非要沿用原来的int返回方式，可以把减法顺序反过来，改成b->frequency - a->frequency，这样频率大的Node会让返回值为正/负，从而排在前面。但这种方式有整数溢出的风险（比如当频率值很大或者有负数时），所以不推荐：

class ComparisonClass { 
public: 
    int operator()(Node *a, Node *b) { 
        return b->frequency - a->frequency; 
    } 
}; 

验证你的示例 #

当你把A(20)、B(4)、C(6)、D(7)入队后，队首到队尾的顺序就是A → D → C → B，完全符合你的需求！

内容的提问来源于stack exchange，提问作者user9506206