3

In C++ Sort function, the third optional parameter is a comparator used to sort the objects. If we pass in less as the comparator, we will get objects in increasing order. (if the comparator is evaluated to be true, the positions won't be changed, otherwise elements will be swaped!) Is my understanding correct?

Following the same fashion, if we pass a less comparator to priority queue, we should get a min-heap,(if the underlying data structure is chosen to be vector, objects are sorted in increasing order. If we call top(), the first element of vector will be returned, which is the smallest number. Therefore, I think it is a min heap) why do we get a max heap?

Zixin Liu
  • 59
  • 5
  • 1
    The first part of your statement is correct. However to get a min heap you'd need to pass `std::greater` otherwise by default `std::less` creates max heap behavior. This is stated in the [documentation](https://en.cppreference.com/w/cpp/container/priority_queue) – Cory Kramer Jul 04 '18 at 18:06
  • Note that the assumption that returning true leaves the order unchanged is not valid. The two items are not required to be passed in the same order as their appearance in the original vector. – Raymond Chen Jul 04 '18 at 19:28
  • `std::priority_queue` is simply a max heap by default. There isn't really more to explain. – eesiraed Jul 04 '18 at 23:14

1 Answers1

1

According to this online documentation, the C++ library class std::priority_queue returns the largest element first in the sense that the comparator orders smaller elements before larger elements. From above link:

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.

Thus std::priority_queue<T,std::less<T>> makes a max-heap and prioritizes larger elements.

Walter
  • 44,150
  • 20
  • 113
  • 196