C++ 优先队列，大顶堆的比较器是less，
来源：4-5 基础堆排序和Heapify
怀瑜
2021-05-31
波波老师你好，很久之前买过这门课，也是在这门课的影响下重视起了对于数据结构的学习，目前我在国内知名adas公司做视觉算法，感谢波波老师！
近期遇到了一个问题，之前我在使用c++内部排序算法sort时，我这样理解sort的第三个参数对"大小"的比较：
struct compare{
bool operator()(int left,int right){return left<right;}//升序
}
在经过"sort"算法处理后的序列里，left是左侧元素，right是右侧元素，这样可以很好理解为什么这里使用"<“得到的升序排列。
同样的道理适用于set和map，但是在priority_queue中却和这边逻辑完全相反，”<"得到的是大根堆，请问这里面的设计思想是什么？我找了很多答案没有找到为什么这样设计？
按照我的理解，如果我们依次取出堆顶元素，那么最left的是堆顶元素，它应该是最小的。
我只能理解实际操作中，为了算法的高效，STL对Heap的实现，right才是堆顶元素。请波波老师指教。
1回答
-
liuyubobobo
2021-06-01
C++ 的 priority_queue 默认实现就是最大堆，也就是“值越高的元素，优先级越大”。所以，< 对于最大堆；less 对应最大堆；> 对应最小堆，greater 对应最小堆。
这本身是符合“优先级”这个概念的语义的，即“优先级高”对应“值大”。“高”和“大”相对应。
当然，就像排序一样，什么叫优先级高应该是可以自定义的。存在很多语言的标准库，使用反向的设计，即 priority_queue 默认是最小堆，比如 Java 语言和 python。我相信这其中的原因，就是这样设计更符合“直觉”，就像你说的，传入 < 返回的是最大值，似乎乖乖的。但这只是一种定义而已，了解背后到底是最大堆还是最小堆就好了。
说实话，当初学 Java，我是很不习惯 Java 的 Priority Queue 默认是最小堆的：）
继续加油！：）
00
相似问题