Why would a min-heap be preferable to a max-heap to implement a priority queue?

1
votes

In a book I am using to study about algorithms and data structures it is stated that a min-heap is preferable to a max-heap to implement a priority queue. Why is that the case?

And why is it a good idea to use a heap to implement a priority queue?

2
algorithmdata-structuresheappriority-queue
Really, it's no more and no less "better" as using a min function instead of a max one. – Gassa
Your 'algorithms and data structures book' such as what? and what exactly does it say? – user207421
@NoProg Can you please add to your question in which book (chapter, page, edition, etc) it's written such a thing? – nbro
Introduction to data structures and algorithms (Cormen, Leiserson, Rivest, Stein) second edition, I think it was chapter 6 (can't remember, i read it at the library) and while he's describing heap types it says something like "min-heap are usually used in priority queue bla bla" but doesn't say why! – NoProg

2 Answers

3
votes

Min-heap is required for more algorithms, such as Dijkstra's. But in reality min-heap and max-heap are equivalent if you just negate all the elements.

A heap is a simple and efficient way to implement a priority queue, since (by nature of the heap) it keeps itself "sorted" as you add/remove from it, therefore giving you fast insertion and removal of the minimum element (if a min-heap). These are precisely the operations a priority queue needs, so a heap is a good fit.

0
votes

You use whichever is necessary. Sometimes 1 is the "highest priority," followed by 2, 3, 4, etc. In that case, you would use a min-heap for your priority queue. Other times, "highest priority" is defined such that the higher numbered thing is processed first. In that case, you would use a max-heap.

A min-heap ensures that the lowest-valued thing is at the root of the heap, and will be removed first when you pull from the heap. A max-heap ensures that the highest-valued thing is at the root of the heap.

You could, of course, always implement a min-heap and, if you need the highest valued thing to be the root, just invert your comparison function.