CODEWITHSUNDEEP
algorithmpriority-queue
Mohamed Horani
Mohamed Horani

Reputation: 554

Priority queue increase-key opeartion

Here is the pseudocode for increase-key operation assuming we are using Max-heaps 

if key < a[i]
then return an error, because key is less than the current key
else
a[i] = key
while i > 1 and a[parent(i)] < a[i]
swap a[i] with a[parent(i)]
i <- parent(i)

According to cormen algorithm book, i can't decrease the key, if i'm using max heaps, but what is stopping me from doing that? i know the if condition won't let me decrease the key.

But let's assume i want to decrease a certain value in a max-heap , after doing that i apply heapify operation, then i can decrease a key even if i'm using max-heaps. which guarantees the properties of max-heap

What is wrong with this assumption?

EDIT heapify function is similar to building a heap function from a given array. but instead of building the whole heap from ZERO, we can heapify it from a certain node.

Upvotes: 2

Views: 3080

Answers (2)

amanmehara
amanmehara

Reputation: 134

Generally in Max-Priority queue we would like to increase the priority of an element, in order to extract that first.

That is why in general Max-Priority queue API only has Increase-Key method / function and not Decrease-Key.

But you definitely can have a Decrease-Key method / function in your own implementation.

Upvotes: 0

Sorin
Sorin

Reputation: 11968

The pseudo code is for a heap pull. That means the node can only go towards the root. If you want to decrease the key then you need to implement a push operation (you push the node down into the heap). It's fairly similar but you need to pick the max between the node's children. Look it up in your book, it should be there.

So, it's possible and fairly efficient but you need more code. There might be external requirements that we don't know. Also note a heap push is O(logn), heapify might check the entire heap, so O(N).

Upvotes: 2

Related Questions