Modifying a heap in O(lgn) time

Question

I've been trying to figure this out for a couple days now. I have a problem for school that says the following:

Let A be a min-heap. The operation HEAP-MODIFY(A, i, k) changes the key in the node i to a new value k, then rearranges the elements in a min-heap. Give an implementation of the HEAPMODIFY that runs in O(lgn) time for an n-element min-heap.

Since we have to design an algorithm that runs in O(lg(n)) time, I know that I can't just iterate through each element. I have the following solution but I am not sure if it is correct.

HEAP-MODIFY(A,i,k):
    A[i] = K

    if A[i] < A[i/2]
        while A[i] < A[i/2] and i > 1
            exchange A[i], A[i/2]
            i=i/2
    else if A[i] > A[2*i]
    while A[i] > A[2*1] and i <k
        exchange A[i], A[2*i]
        i = 2*1

Any suggestions as to how this can be tackled?

Answer 1

You're thinking in the right direction but the operations you perform won't guarantee a min-heap as the result. Look at the following heap:

  ..
  11
 /  \
19  63 (<-was 13)
.. /  \
  55  15
  ..  ..

Imagine you just updated the key 13 to 63 and want to restore the min-heap property. Your code would swap 55 and 63 because 55<63, but than 55 would be the parent of 63 and 15(!) and therefore hurt the min-heap property.

The function you need (to restore the min-heap property) is called "heapify". It isn't trivial, but it also isn't very complex. Look up its explanation in this wikipedia article about heapsort. There is nothing wrong in just reading/learning the solution as long as you understand it and not just copy it.

If you still have questions afterwards, ask.

Answer 2

You can find and remove Node(i), change the value of the Node to k and put it back into the heap. This is not the most efficient way to go, but it's still log(n). The advantage is that it's simple and will likely reuse operations you've already implemented.