Bubble a New Value Up With heapify_up
Bubble a New Value Up With heapify_up
Complete heapify_up. It takes the index of a value that may be smaller than its parent and moves that value up the tree, one swap at a time, until the min heap rule holds again. It returns nothing: it rearranges heap->data in place.
Reminder: why a new value has to bubble up. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps, and every parent is smaller than or equal to its children, so the smallest value is at index 0. Insert adds the new value at the end, in the first empty slot, so the tree stays complete. The only pair that can now break the rule is the new value and its parent at (i - 1) / 2. If the new value is smaller, the two trade places and the same question is asked one row higher: that is heapify up.
Here 2 has just been added to the end of the heap 3 6 5 10 8 9:
Step 1: 2 went into the first empty slot, index 6.
Its parent is index (6 - 1) / 2 = 2, which holds 5.
3
/ \
6 5
/ \ / \
10 8 9 2 2 is new, at index 6
Step 2: 2 < 5, so swap index 6 with index 2.
Now i = 2. Its parent is index 0, which holds 3.
3
/ \
6 2 2 moved up to index 2
/ \ / \
10 8 9 5
Step 3: 2 < 3, so swap index 2 with index 0.
Now i = 0, the root, so the loop stops.
2 2 reached the root
/ \
6 3
/ \ / \
10 8 9 5
index: 0 1 2 3 4 5 6
before: 3 6 5 10 8 9 2
after: 2 6 3 10 8 9 5Not every value travels that far. If the new value had been 4, step 3 would find that 3 is not bigger than 4 and stop with 4 at index 2. A value that is already greater than or equal to its parent does not move at all.
Requirements:
1. heapify_up(heap, i) swaps the value at index i with its parent while i is greater than 0 and the value is smaller than its parent's value. After each swap, i becomes the parent index.
2. Stop at the root: when i is 0 there is no parent to compare with.
3. Stop as soon as the value is greater than or equal to its parent. Equal values do not swap.
4. Use get_parent_index and swap. Only values on the path from i up to the root move, and heap->size does not change.
5. Leave the MinHeap struct and the provided functions (heap_init, heap_load, get_parent_index, swap, heap_print) as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 4 8 6 12 9 7 10 placed 1 at index 7 MinHeap: 4 8 6 12 9 7 10 1 heapify_up from index 7 MinHeap: 1 4 6 8 9 7 10 12 placed 5 at index 8 MinHeap: 1 4 6 8 9 7 10 12 5 heapify_up from index 8 MinHeap: 1 4 6 5 9 7 10 12 8
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...