我想知道为什么要使用 priority_queue
创建最小堆,应该使用 std::greater
?
std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;
对我来说,因为最小值总是位于堆的顶部,所以所使用的类应该是 std::less
更新:
另一方面,由于 priority_queue
(最大堆)的默认行为是在顶部保存最大值,所以在我看来 std::greater
应该用于最大堆创建而不是最小堆创建
最佳答案
逻辑论证如下
std::priority_queue
是容器适配器;基本内存考虑使背面成为序列容器(如std::vector
)修改的首选位置(使用pop_back()
和push_back()
) >。priority_queue
基元基于std::make_heap
(构造函数)、std::pop_heap
+container::pop_back
(priority_queue::pop
) 和container::push_back
+std::push_heap
(priority_queue::push
)pop_heap
将获取底层存储的前面,并将其放在后面,之后恢复堆不变性。push_heap
则相反。- 在
max_heap
上执行sort_heap
(最初最大值在前面)将 repeatedly pop the front to the back并根据less
(这是默认的比较运算符) 对范围进行排序
- 因此,
max_heap
的首选实现是让最大元素 w.r.t.less
在前面,通过priority_queue::top
访问(底层container::front
)。 - 人们仍然可以争论
priority_queue
与std::less
比较器代表max_heap
是否直观。它可以定义为min_heap
通过在调用各种堆函数的任何地方反转比较器的参数(但请参阅 @T.C. 的评论,对于 C++98 绑定(bind)器,这是相当冗长的)。一个(对我来说)违反直觉的结果是top()
不会给具有 top 优先级的元素
关于c++ - 使用 `std::greater` 通过 `priority_queue` 创建最小堆的原因,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59023970/