CODEWITHSUNDEEP
algorithmdata-structures
Qiang Li
Qiang Li

Reputation: 10865

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

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?

Upvotes: 13

Views: 2860

Answers (3)

svick
svick

Reputation: 244968

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.

Upvotes: 3

chill
chill

Reputation: 16898

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

Upvotes: 3

mcdowella
mcdowella

Reputation: 19611

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.

Upvotes: 1

Related Questions