使用`std :: greater`通过`priority_queue`创建最小堆的原因 [英] The reason of using `std::greater` for creating min heap via `priority_queue`

问题描述

我想知道为什么要使用 priority_queue 创建一个最小堆，应该使用 std :: greater ？

I am wondering why for creating a min heap using the priority_queue, the std::greater should be used?

std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;

对我来说，由于最小的值总是位于堆的顶部， std :: less

To me, since the smallest value is always located at the top of the heap, the employed class should be std::less

更新：
另一方面，因为 priority_queue （max heap）的默认行为是在顶部保持最大的值，它看起来我认为 std :: greater

Update: On the other hand, since the default behavior of priority_queue (max heap) is to hold the greatest value at the top, it looks to me that the std::greater should be used for the max heap creation and not for min heap creation

推荐答案

逻辑参数是如下

1. std :: priority_queue 是容器适配器;基本内存考虑使后面成为修改的首选位置（对于序列容器使用 pop_back（）和 push_back（））例如 std :: vector 。


2. priority_queue 基元是基于 std :: make_heap （构造函数） ， std :: pop_heap + container :: pop_back （ priority_queue :: pop ）和 container :: push_back + std :: push_heap （ priority_queue :: push ）


3. pop_heap 会采用底层 存储，并将其放在后，以后还原堆不变量。 push_heap 。 c $>
   
4. sort_heap $ c> max_heap （最初的最大值）将反复弹出前面的 a>并根据 less （这是默认的比较运算符）


5. 对范围进行排序，因此， c $ c> max_heap 是最大元素wrt 在前面，通过优先级队列:: top （底层 container :: front ）。


6. 仍然可以讨论 priority_queue 与 std :: less comparator表示 max_heap 。它可以被定义为 min_heap 通过逆转比较器的参数（但是看到@TC的注释，使用C ++ 98绑定器，这是相当冗长）在呼叫到各种堆函数。一个（对我来说）反直觉的结果将是 top（）然后不会给予顶部优先级的元素

1. std::priority_queue is a container adaptor; basic memory considerations make the back the preferred place for modifications (with pop_back() and push_back()) for sequence containers such as std::vector.
2. the priority_queue primitives are based on std::make_heap (constructor), std::pop_heap + container::pop_back (priority_queue::pop) and on container::push_back + std::push_heap (priority_queue::push)
3. pop_heap will take the front of the underlying storage, and put it at the back, restoring the heap invariant afterwards. The reverse goes for push_heap.
4. doing sort_heap on a max_heap (with the max at the front initially) will repeatedly pop the front to the back and sort the range according to less (which is the default comparison operator)
5. hence, the preferred implementation of a max_heap is to have the max element w.r.t. less at the front, accessed through priority_queue::top (underlying container::front).
6. one can still debate whether it is intuitive that priority_queue with a std::less comparator is representing a max_heap. It could have been defined as a min_heap by reversing the comparator's arguments (but see the comment by @T.C. that with C++98 binders this is rather verbose) everywhere in the calls to the various heap functions. The one (for me) counter-intuitive result would have been that top() would then not have given the element with top priority

这篇关于使用`std :: greater`通过`priority_queue`创建最小堆的原因的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！