Modified algorithm for Max-Heapify

Question

in a question I have to answer they asking to write an algorithm Modified-Max-Heapify for a random value insertion.enter image description here The question is in below link. Can anyone help me to figure this out?

Answer 1

I'm not going to do your homework for you, but here's a hint. Suppose that instead of A[i] being set to a random value, you were told that A[i] was set to a value that was larger any other item in the heap. Let's call it ∞. Would you know how to fix up the heap? Remember that in your fixed up heap, whatever is in A[i] has to percolate to A[0], since it's the largest element.

If you can do that, you can now solve the original problem.

1. temp = A[i]
2. A[i] = ∞
3. Fix up the heap using what you figured out above.
4. Remove the largest element of the heap, which we know is the ∞ we put into A[i] in step 2.
5. Add temp to the heap using standard heap algorithms.

---

There is a faster but more complicated way of doing this. Remember that every help of a max-heap is smaller than its parent and bigger than its children.

If an element is too big for its spot, you can repeatedly move it up the tree, swapping it with its parent, until the element reaches the root or is smaller than its parent.

If an element is too small for its spot, you can repeatedly move it down the tree, swapping it with its largest child, until the element has no children or is larger than its children.

If the structure is a heap except for the spot where your element is, it is easy to show that it remains a heap, except for the spot where your element has moved it, after a swap.

Code this.