Why does priority queue (max heap) in C++ use less<T> instead of greater<T>?

Jimmy (xiaoke) Shen
1 min readMay 31, 2021

--

The question can be found from [1]. I am looking for answers as I also have the same confusion. Why less gives us the largest number (max heap), isn’t it be a minimum number (min heap)?

From the reply of [1], we can see the reason for using less is:

For consistency. less is used as the default comparator for many algorithms and containers, and us mere humans don't have to try and remember which one uses which comparator by default since they are all the same. From [1]

From [2]

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall be accessible through random access iterators and support the following operations:

  • empty()
  • size()
  • front()
  • push_back()
  • pop_back()

So the real reason should be:

As for priority_queue we may not only find the top element, but also pop the top element. Those operations are related to push_back and pop_back. So when we use less the organize the numbers, somehow, the largest one will be at the end. It explains why using less giving us the max heap.

Reference

[1]Why does priority queue (max heap) in C++ use less<T> instead of greater<T>?

[2] http://www.cplusplus.com/reference/queue/priority_queue/

--

--

No responses yet