The reason of using `std::greater` for creating min heap via `priority_queue`

Question

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

Durgy

Where are you looking? I am reading cppreference.com right now and they specify std::less as the default and say substituting std::greater would cause the smallest element to appear as the 'top' rather than the greatest. Just seems to be a matter of convention, no? – Tarttan

I think this is an excellent question. I find it odd I found so few people questioning this specific design decision. So far, you were the only one that, like me, seems to find it very counter-intuitive this "reverse" usage of the comparator. I won't question the performance reasons behind the decision, but it does not fell natural to me. – Odle

I just ran into this myself while answering another question and it feels especially unnatural when writing your own comparators. – Osmo

It's kinda odd. heapify_down is: if greater, then move it down. and heapify_up: if it's not greater, then move it up. – Atmolysis

Answer 1

The logical argument is as follows

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

Teleost

The meow_heap algorithms are definitely in C++98. – Proserpina

@Proserpina you are right, updated, only is_heap and is_heap_until were added – Teleost

Also, you can't negate the comparator; you need a wrapper that swaps the order of arguments. Given how primitive C++ TMP was at the time this was originally designed (think all the ptr_fun/bind1st/bind2nd fun), I'm not really surprised they didn't do it. – Proserpina

@Proserpina yes, easy to forget the pain of the old binders and also having to extract first_argument_type and second_argument_type – Teleost

Can someone explain point 5 again ? From what I understood, popping the element from the max_heap is done from the back. So as less orders the elements in ascending order, getting the top element removes the element from the back ? Have I understood it correctly ? – Biology

@Biology no, as point 3 indicates (and see this documentation), pop_heap will take the front and place it at the back. – Teleost

@Teleost So how does less order it in decreasing order such that the max element is a the top ? – Biology

@Biology the implementation of pop_heap uses something called sift_down (and push_heap uses sift_up). You can go look at the libc++ implementation on GitHub or for a more didacted explanation here. – Teleost

Answer 2

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.

Dov

This doesn't answer the question why using less induces a max-heap, while greater induces a min-heap. – Imperialism

See my edits, but the TL;DR is max-heaps are used elsewhere in C++ so they are the default. – Dov

So, lemme see if I understood you correctly. You meant since less is the default comparator and since max_heap is more useful, we ended up having a max_heap that implemented via less instead of greater? – Durgy

I don't think a max-heap is any easier to implement than a min-heap using less. However, it is certainly easier (and more efficient) to implement std::sort_heap from a max-heap, assuming you want the same ordering you would get from std::sort, using the same comparison operator. That fact may have contributed to the reasoning. – Vaish

@TemplateRex: Because when you pop an element off the heap, you are left with a space at the end, where you can place the element you just popped off (which is the greatest element). In order to get the correct order if you started with a min-heap, you would have to reverse the range when you were done. – Vaish

@TemplateRex: It seems to me that implementing push_heap and pop_heap would be very inefficient with that configuration, unless you used push/pop_front instead of push/pop_back. But then you couldn't use a vector as the underlying container. – Vaish

@BenjaminLindley summarized this comment conversation into a new answer. – Teleost

Answer 3

It is a process that transforms a priority queue into a sorted sequence.

How can we achieve this?

Suppose we have a max heap now, we take the following procedure.

HEAP-SORT(A)
    for i = A.heap_size downto 2
        exchange A[1] with A[A.heap_size]
        A.heapsize -= 1
        max_heapify(A)

When we finish this procedure, we get an increasing order sequence.

We notice every time when we compare two elements, we always put the larger one to the array back, which implies the smaller one is on the left of the bigger one.

And this matches the idea when we pass a less operator to the std::sort algorithm to get an increasing order sequence.

Constancy

Answer 4

A priority_queue is a data structure that stores elements in a way that the element with the highest priority is always at the top of the queue. By default, the priority of an element is determined by its value. However, you can use a functor to change the way that the priority of an element is determined.

A functor is a small function object that can be used to perform a specific task. In this case, the greater<int> functor is used to compare two integers and return true if the first integer is greater than the second integer.

When you use the greater<int> functor with a priority_queue, the element with the lowest value will be considered to have the highest priority. This is because the greater<int> functor will always return true when comparing the element with the lowest value to any other element.

Beast

Answer 5

From cppreference

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Compare - A Compare type providing a strict weak ordering. Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.

Leech