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.

 

[DeeNos]

This is a good start to your solution, but it does not run in O(lgn) time. In order for this operation to run in O(lgn) time, you will need to use the properties of a min-heap to efficiently rearrange the elements. One way to do this is by using a recursive approach.

Here is a possible solution in pseudo code:

HEAP-MODIFY(A, i, k)
A = k
if A < A[parent(i)]
MIN-HEAPIFY(A, i)
else
MAX-HEAPIFY(A, i)

MIN-HEAPIFY(A, i)
if A < A[parent(i)]
exchange A, A[parent(i)]
MIN-HEAPIFY(A, parent(i))

MAX-HEAPIFY(A, i)
if A > A[parent(i)]
exchange A, A[parent(i)]
MAX-HEAPIFY(A, parent(i))

In this solution, the MIN-HEAPIFY and MAX-HEAPIFY functions recursively compare the key at index i with its parent and swap them if necessary. This is done until the key reaches its correct position in the heap, which will have a runtime of O(lgn).

Overall, the HEAP-MODIFY function will have a runtime of O(lgn) since it only makes a constant number of calls to MIN-HEAPIFY or MAX-HEAPIFY.