Why does the highest priority queue have a DECREASE-KEY?

Question

When discussing the heap data structure, for example, in CLRS , only the INSERT, MAXIMUM, EXTRACT-MAX, and INCREASE-KEY are needed for the queue with the highest priority. But why doesn't he also have a DECREASE-KEY, at least will his work also invalidate the heap property? Is it practically unimportant?

Answer 1

Nothing prevents you from implementing DECREASE-KEY on your binary heap. This can be done in O (log N) without breaking any invariants.

I assume that it is not included, because it is not needed very often.

Answer 2

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

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

Answer 3

If you have MAX-HEAP, DECREASE-KEY will be MAX-HEAPIFY in section 6.2 “Saving Heap Properties” CLRS 3rd Edition.