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?

Polyamide

O (lg(n)) is code for "divide and conquer". You need to split the problem into two parts: one that is already solved, and one that needs to be solved. Since the already solved is done, no work to do. Does your algorithm properly divide and conquer? Update your question to explain how you're dividing and conquering so we can comment on that. – Fawcett

Answer 1

HEAP-MODIFY(A,i,K) 
A[i] = K 
MIN-HEAPIFY(A,1)

I am also working on this problem, and got this. I'm just as confused as you are though, but I feel your code is overcomplicated it up above.

Erbil

See, that was my first instinct too. The A[i] = K command is a constant operation, and MIN-HEAPIFY is an O(lg(n)) operation. – Polyamide

Answer 2

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.

Minos

Thanks! I had a feeling I had to use MIN-HEAPIFY, since it runs at O(lg(n)) but it just felt way too easy. There are no constraints to the problem however. Either way, I still need to sit down and think about it and really understand it. – Polyamide

@saullawl the heapify function really isn't hard to understand: It basically does what your code was doing: moving keys up as long as they are smaller than their parents (because thats how a min-heap is defined). It's just so that you overlooked that by moving keys up you could hurt the min-heap property at new places where it was fulfilled before. So heapify repairs those parts. – Minos

Originally I had the following: HEAP-MODIFY(A,i,K) A[i] = K MIN-HEAPIFY(A,1) Was I over-engineering this? – Polyamide

Answer 3

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.

Carrion