Why doesn't max-priority queue have DECREASE-KEY?

11
votes

In the discussion of heap data structure, for example in CLRS, the max-priority queue only needs INSERT, MAXIMUM, EXTRACT-MAX, and INCREASE-KEY. But why doesn't it also have DECREASE-KEY, at the least, its operation will also invalidate the heap property? Is it practically unimportant?

3
algorithmdata-structures
I would think this is related to how min-priority queues don't usually have INCREASE-KEY, even though it is a perfectly well-defined operation. My guess is that this is just something that doesn't arise much. Also, w00t on getting exactly 1337 reputation! - templatetypedef
I could swear I asked this exact question before but I can't find it. - Jason S
cs.stackexchange.com/questions/10203/… - max

3 Answers

3
votes

If you have a MAX-HEAP, DECREASE-KEY will be MAX-HEAPIFY in section 6.2 "Maintaining the heap property" of CLRS, 3rd edition.

3
votes

Nothing is stopping you to implement DECREASE-KEY in your binary heap. It can be done in O(log N) without breaking any invariants.

My guess is that it isn't included, because it's not needed very often.

1
votes

FWIW my CLR V1 talks about INSERT, MIN, EXTRACT-MIN, UNION, DECREASE-KEY, and DELETE, but we can convert to your version by flipping signs.

I think this set is driven by the requirements of the algorithms that use priority queues, such as minimum spanning tree, Dijstra shortest path, and (I suspect) A*. For instance, if you look at the start of the chapter on minimum spanning trees, you can see a note that Prim's algorithm can be sped up if you replace binary heaps with fibonacci heaps.