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;
To me, since the smallest value is always located at the top of the heap, the employed class should be std::less
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
The logical argument is as follows
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
. 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
.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)max_heap
is to have the max element w.r.t. less
at the front, accessed through priority_queue::top
(underlying container::front
). 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