本文介绍了使用`std :: greater`通过`priority_queue`创建最小堆的原因的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我想知道为什么要使用 c $>
- 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.
- 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)
- 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.
- 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)
- 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).
- 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`创建最小堆的原因的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!