How Do You Modify a Key in a Min-Heap to Maintain Heap Properties?

[gotem3303]

Homework Statement

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.

Homework Equations

The Attempt at a Solution

Ive been trying to work this one for over a day and can't seem to get it. I am pretty sure there will need to be 2 cases, one where the key has been increased and one where the key has been decreased. This would be determined by comparing the new value to the node with indexes i+1 and i-1. However, that's where I am stuck.

The only solution I've found that would work is if I took the new value and went through a loop that did the following:

1. Check the node with index i-1, if new value is less then exchange the keys
2. Same as above, but with index i+1, and if the new value is larger than this one exchange them
3. Continue this loop until the new key is where it should be

However, I don't know what the RT would be for the above algorithm, but I am guessing O(n)? This would the Psedo Code I came up with

HEAP-MODIFY(A, i, k)

A[i] = k
if increased
  while A[i+1] < k and i > 1
     exchange A[i], A[i+1]
     i=i+1
else if decreased
  while A[i-1] > k and i < A.length
    exchange A[i], A[i-1]
    i=i-1

 

[Zomg]

You are so in my class.

Guess all the analysis of algorithm newbs are going to forums for answers.

 

[verty]

I think you will need to say more about the implementation of your min-heap. The O(lgn) bound assumes a divide-and-conquer access pattern.

 

[sourlemon]

The question you have to ask yourself is, what are the properties of a min heap? Is it a binary heap tree? After listing all the properties of the heap tree, I would draw a heap tree out, then randomly insert a number in one of the node, then check to see how I would modify it to make it a heap tree again. After doing that by hand, think about the tree in a one dimensional array. Hopefully that will be some help for you. The important thing is you have to know what makes A a min-heap.

I wouldn't worry about the run time just yet.