- #1
gotem3303
- 29
- 0
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:
- Check the node with index i-1, if new value is less then exchange the keys
- Same as above, but with index i+1, and if the new value is larger than this one exchange them
- 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)
Code:
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