Final answer:
Restoring a heap after replacing a value at index i involves heapifying the array again. This is done either by bubbling-up if the new value is out of place among its ancestors or by sifting-down if it's out of place among its descendants, depending on the type of heap (max or min).
Step-by-step explanation:
Restoring a Heap
When replacing a value in a heap, the resulting array may not satisfy heap properties. To restore these properties, you'll need to implement a procedure that will reorder the elements accordingly. The algorithm differs slightly depending on whether it's a max-heap or min-heap, but the general idea involves what's called heapify.
In a max-heap, for example, if the new value at index i is greater than its parent, you'll need to propagate the value up the tree using a series of swaps—this is sometimes referred to as heapify-up or bubble-up. Conversely, if the new value is less than either of its children, the algorithm must push the value down using a process known as heapify-down or sift-down.
The general algorithm for a max-heap is as follows:
- Replace the value at index i with the new value.
- If the new value is greater than its parent, swap it with the parent until the new value is at the correct position or has reached the root.
- If after replacement, the new value is smaller than its children, compare it with its children and swap it with the larger child if necessary. Repeat this step until the value is in the correct position or it has no children.
For a min-heap, follow the same steps but inverse the comparisons: propagate up if the new value is smaller, and sift down if it’s greater than its children.