Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question

migrated from stackoverflow.com May 17 '11 at 12:16

This question came from our site for professional and enthusiast programmers.

    
Aren't they exactly the same thing ? I vote to close as argumentative. –  Alexandre C. May 17 '11 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 May 17 '11 at 11:53
1  
@LaC: you can use std::not2(std::less<T>()). –  Alexandre C. May 17 '11 at 11:57
add comment

4 Answers 4

up vote 8 down vote accepted

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.

share|improve this answer
1  
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. –  Martín Fixman May 17 '11 at 14:11
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
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 May 17 '11 at 11:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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