Question

Consider an array that represents a heap. Suppose that you replace the value at index i with a new value. It is likely that you will no longer have a heap. Write an algorithm that will give you a heap again. You need to rebuild the semiheap rooted at the new value to get a heap. The algorithm assumes that the n values in the heap are stored in an array at indices 1 to n//Algorithm to fix heap if a change occurs at changeIndex: You need to use a while loop

Answer 1

Restoring a heap after updating a value at a specific index involves sifting the value up or down, depending on whether the value was increased or decreased.

Step-by-step explanation:

To restore a heap property in an array after altering a value at a given index, you will need an algorithm that either sifts the changed value up or down the heap. Such action is necessary to maintain the semi-heap property following the replacement.

Let's assume we have a max-heap. When a value at index 'i' is changed, we compare it with its parent if the value is increased (or with its children if the value is decreased), and decide whether to sift up or sift down, respectively:

1. Compare the new value with its parent; if it's greater, then sift up:

• While 'i' is greater than 1 and the new value is greater than the value at i/2 (the parent index):
• Swap the new value with the value at i/2.
• Update 'i' to be i/2, making it the new index of the sifting value.

If the new value is less than its original or if it's already less than its parent, sift down:

• While i has at least one child and the new value is less than one of its children:
• Find the greater child.
• Swap the new value with this greater child.
• Update 'i' to be the index of the child where the swap occurred.

This process continues until the new value is less than its parent (for sift down) or until it doesn't have children greater than itself (for sift up), thus re-establishing the heap invariant.The aim is to maintain the parent-child relationship of the heap, either by ensuring the new value is smaller than its parent (min-heap) or greater (max-heap). This is done through a while loop and conditional swaps until the heap property is satisfied.