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. - 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
The C++ heap functions make_heap, push_heap, and pop_heap operate on a max heap, meaning the top element is the maximum when using the default comparator. So, to create a min-heap, you need to use greater<T> instead of less<T>.
I suspect that a max heap is used instead of a min heap is that it is easier to implement with the less operation. In C++, less has the special privilege of being the sort of "default" comparator for all STL algorithms; if you only are going to implement one comparison operation (other than ==), it should be <. This leads to the unfortunate quirk that priority_queue<T, C<T>, less<T>> means a max-queue and priority_queue<T, C<T>, greater<T>> means a min-queue.
Also, certain algorithms like nth_element need a max-heap.
See http://en.cppreference.com/w/cpp/container/priority_queue. A priority_queue is designed to put the largest value at the top. This happens if you use the default std::less comparator. So if you want the reverse behavior, you need to use the reverse comparator, std::greater.
