Remove a Chosen Value From Anywhere in the Heap
Remove a Chosen Value From Anywhere in the Heap
The lab can only remove the root. Write min_heap_remove_value, which removes a value you name, wherever it sits. It returns true when the value was found and removed, false when it is not in the heap. heapify_up and heapify_down are 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.
A heap is not sorted, so finding the value means checking the slots one by one, from index 0. Removing it uses the same trick as removing the root: the LAST value moves into the hole, so the tree stays complete. The difference is what happens next. At the root a moved value can only be too big, so it sinks. In the middle of the tree it can also be too SMALL for its new parent, so it may have to climb instead.
remove 8 from 1 4 2 8 5 3: remove 4 from 1 4 2 8 5 3:
the last value (3) fills the hole the last value (3) fills the hole
1 1
/ \ / \
4 2 3 2 3 has children 8 and 5:
/ \ / \ nothing to fix this time
3 5 3 < 4: it must CLIMB 8 5
1
/ \
3 2
/ \
4 5You do not have to work out which direction is needed. Call heapify_up on the slot and then heapify_down on the same slot: at most one of them moves anything.
Requirements:
1. Find the first slot (lowest index) that holds value. When no slot does, return false and change nothing.
2. Subtract 1 from count, then copy the value from the old last slot into the slot you found.
3. When the slot you found was not the old last slot, call heapify_up and then heapify_down on it.
4. Return true. Only one copy is removed when the value appears more than once.
Do NOT write a main function.
Expected Output:
remove 9: yes [1, 4, 2, 5, 6, 3] remove 1: yes [2, 4, 3, 5, 6] remove 6: yes [2, 4, 3, 5]
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...