Replace the Smallest Value in One Step
Replace the Smallest Value in One Step
Complete heap_replace_min(MinHeap *heap, int value, int *old_min). It takes the smallest value out and puts value in, in a single step: the old root goes into *old_min, the new value goes into the root, and the function returns 1. On an empty heap it returns 0 and changes nothing.
Reminder: remove and insert in a min heap. 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. Remove takes the root, moves the last value to the root and sinks it down (heapify down) by swapping with the SMALLER child. Insert adds at the end and bubbles up (heapify up).
heap_replace_min(heap, 10, &old_min) on this heap:
index: 0 1 2 3 4 5 6
value: 2 6 3 9 7 5 8
2 old_min gets 2, the old smallest value
/ \
6 3
/ \ / \
9 7 5 8
step 1: 10 goes straight into the root
10 bigger than its children 6 and 3: sink it
/ \
6 3
/ \ / \
9 7 5 8
step 2: heapify_down swaps 10 with the smaller child 3, then with 5
3
/ \
6 5
/ \ / \
9 7 10 8 10 reached a leaf, and the size is still 7
index: 0 1 2 3 4 5 6
value: 3 6 5 9 7 10 8Compare that with heap_remove followed by heap_insert. The remove would sink the last value (8) from the root down to a leaf, then the insert would put 10 at the end and compare it with its parent, and a smaller value could have to climb all the way back to the root: two trips through the tree in the worst case. Writing the new value straight into the root needs only the one trip down, and the size stays the same the whole time.
Requirements:
1. Return 0 when the heap is empty, and change nothing: not the heap and not *old_min.
2. Otherwise put the current root (the smallest value) in *old_min, write value into index 0, and call the provided heapify_down(heap, 0) so the new value sinks to its place.
3. Return 1. The size does not change, so a full heap stays full.
4. value may be smaller than everything already in the heap. Then it stays at the root and nothing else moves.
5. Leave heapify_down and the other helpers as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 1 3 2 6 4 5 9 10 7 8 12 11 14 13 15 replace with 20: yes, old min was 1 MinHeap: 2 3 5 6 4 11 9 10 7 8 12 20 14 13 15 replace with 1: yes, old min was 2 MinHeap: 1 3 5 6 4 11 9 10 7 8 12 20 14 13 15 size: 15
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...