Change a Value Inside the Heap
Change a Value Inside the Heap
Complete heap_change_value(heap, i, new_value). It overwrites the value at index i with new_value, moves it until the heap rule holds again, and returns 1. When i is not an index inside the heap it returns 0 and changes nothing.
Reminder: a change can only break the rule in one direction. 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. Insert fixes a new value by bubbling it up (heapify up), and remove fixes the root by sinking it down (heapify down), swapping with the SMALLER child. Both heapify_up and heapify_down are already written for you, and both work from any index, not just the last slot or the root.
index: 0 1 2 3 4 5 6
value: 1 4 2 7 5 3 8
change index 6 (the 8) to 0: 0 is smaller than 8, so it may need to go UP
after writing 0 after heapify_up
1 [0]
/ \ / \
4 2 -> 4 1
/ \ / \ / \ / \
7 5 3 [0] 7 5 3 2
0 < 2: swap. 0 < 1: swap. 0 is at the root: stop.
index: 0 1 2 3 4 5 6
value: 0 4 1 7 5 3 2
change index 1 to 9 (starting from the first heap again): 9 is bigger than 4, so it may need to go DOWN
after writing 9 after heapify_down
1 1
/ \ / \
[9] 2 -> 5 2
/ \ / \ / \ / \
7 5 3 8 7 [9] 3 8
9 has children 7 and 5. The smaller one is 5, and 5 < 9: swap. 9 is now a leaf at index 4: stop.
index: 0 1 2 3 4 5 6
value: 1 5 2 7 9 3 8A value that got smaller can only clash with its parent: its children were already at least as big as the old value, so they are bigger than the new one too. A value that got bigger can only clash with its children: its parent was already no bigger than the old value. So compare the new value with the old one: smaller means heapify_up(heap, i), bigger means heapify_down(heap, i), and the same value means there is nothing to fix.
Requirements:
1. Return 0 and change nothing when i is less than 0 or not less than heap->size.
2. Otherwise remember the old value at index i, store new_value there, then fix the heap: heapify_up(heap, i) when the new value is smaller than the old one, heapify_down(heap, i) when it is bigger, nothing when they are equal.
3. Return 1 for every index inside the heap, even when new_value is the same as the old value or the value does not need to move.
4. Leave the struct and every provided helper (heapify_up, heapify_down and the ones they use) as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 2 5 3 8 6 4 9 10 12 change index 8 to 1: yes MinHeap: 1 2 3 5 6 4 9 10 8 change index 6 to 7: yes MinHeap: 1 2 3 5 6 4 7 10 8
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...