Replace the Root Without Changing the Count
Replace the Root Without Changing the Count
Complete min_heap_replace. It takes the smallest value out and puts a new value in, in one step. The old smallest value comes back through the pointer value. heapify_down is already written for you.
Reminder: how this min heap is stored. A min_heap is a struct with three fields: capacity (the most values it can hold), count (how many it holds now) and values (a pointer to an array made with malloc). The heap is a complete binary tree kept in that array, filled row by row with no gaps, so only slots 0 to count - 1 are in use. Every parent is smaller than or equal to its children, so the smallest value is always at index 0. For the value at index i, the parent is at (i - 1) / 2 and the children are at 2 * i + 1 and 2 * i + 2.
You could do this with a remove followed by an insert, but that walks the tree twice: once down, once up. Replace is cheaper. The new value is written straight over the root, and one trip down puts it where it belongs. The number of values never changes.
replace the smallest with 8:
before 8 written over the root 8 sinks past 3, then past 5
1 8 3
/ \ / \ / \
3 4 3 4 5 4
/ \ / \ / \
5 9 5 9 8 9
1 3 4 5 9 8 3 4 5 9 3 5 4 8 9
*value becomes 1, count stays 5Requirements:
1. When the heap is empty, return false and change nothing.
2. Otherwise copy the root into *value, write replacement into index 0, and call heapify_down on index 0.
3. Return true. count must not change.
Do NOT write a main function.
Expected Output:
took out 1 [2, 4, 6, 7, 5] took out 2 [0, 4, 6, 7, 5] count 5
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...