Priority queue increase-key opeartion

Question

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.

Not everybody is familiar with the book. Add what "heapify" is. — Karoly Horvath
I remember I had the same idea when I was reading this and, well.. nothing? It's still going to be O(log n). — Karoly Horvath
Yea it's still going to be O(lg n), but is it going to work ? — Mohamed Horani

Sorin Sorin · Accepted Answer · 2016-03-14T13:48:27

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).

Priority queue increase-key opeartion

2 Answers