I just noticed something and I wonder if there is any reason for that. Except for C++ (std::priority_queue is a max heap), I don't know any other language that offers a max heap.

Python's heapq module implements a binary min-heap on top of a list.

Java's library contains a PriorityQueue class, which implements a min-priority-queue.

Go's library contains a container/heap module, which implements a min-heap on top of any compatible data structure.

Apple's Core Foundation framework contains a CFBinaryHeap structure, which implements a min-heap.

I find a max-heap more intuitive than a min-heap and I believe technically the implementation difference is only a question of changing a comparison operator. Is there any real reason? Most of the applications need a min instead of a max heap? Thanks in advance

  • Aren't they exactly the same thing ? I vote to close as argumentative.
    – Alexandre C.
    Commented May 17, 2011 at 11:50
  • 2
    Just a couple of days ago I needed a min heap in C++ and was a bit annoyed that priority_queue defaults to a max heap. It forced me to define operator > on my custom class, which already had operator <. When working with graphs, you typically want to prioritize the shortest edges, so you need a min heap.
    – LaC
    Commented May 17, 2011 at 11:53
  • 2
    @LaC: you can use std::not2(std::less<T>()).
    – Alexandre C.
    Commented May 17, 2011 at 11:57

4 Answers 4


As others have observed, if the heap accepts a comparator, then it's not too hard to get one behavior or the other. A quick perusal of Google Code, however, suggests that min-heap is by far more prevalent in actual code, because of two applications that come up again and again.

  • Dijkstra/A*/many other shortest path algorithms (because partial paths get longer).

  • Event simulation (because time goes forward).

Also, I would argue that because the default sort returns items small to large, so should the default heap.

  • 2
    I usually program in C++, and wonder the contrary: why does C++ not implement a min-heap? As you said, most algorithms use a min-heap. Commented May 17, 2011 at 14:11

It is just a matter of taste. I don't think there will be any specific reason. It's just like some people like to express optimizing problems as minimizing cost, while others like say maximizing profit.


Most languages I know allow to pass a parameter to decide whether it should be a min- or max-heap. So the default value is somewhat arbitrary. I guess for most languages it is a question of consistency to define what the default operator is. For C++ in the stl the default is std::less leading to a min-heap.

The consistency of using std::less for default everywhere means you only have to implement this comparison when you are using any kind of data structure and you do not have to decide on which data structure you are going to use later when you design your classes. I would guess it is the same for other languages with the only difference that a greater-than comparison is the standard.

  • 3
    I don't think there is such a connection. You can implement either kind of heap using either < or >. Indeed, std::less is the default in STL, but they implement a max heap instead of a min heap.
    – LaC
    Commented May 17, 2011 at 11:49

Basically, the index value is an arbitrary number. If you believe that the number represents a priority, and larger numbers are higher priorities, then a max-heap makes sense. But if the numbers represent, eg, conceptual bakery numbers ("Take a number") then min-heap makes more sense.

You can always convert from one to the other by taking the 1's complement of the index.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.