Remove the Smallest Value From a Min Heap
Remove the Smallest Value From a Min Heap
Complete heap_remove. It takes the smallest value out of the heap, stores it in *removed and returns 1, or returns 0 when the heap is empty. Sinking the moved value back into place is done for you by the provided heapify_down.
Reminder: remove always takes the root. 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. You cannot simply delete index 0, because that leaves a hole at the top. Instead, move the LAST value into the root and shrink the heap by one. The tree stays complete, but the root is now probably too big, and heapify_down fixes that by swapping it with its SMALLER child until no child is smaller.
Here the root 2 is removed from the heap 2 4 3 9 5 6 7:
Before: size 7. The root 2 is the value to hand back.
2 2 goes into *removed
/ \
4 3
/ \ / \
9 5 6 7 7 is the last value, index 6
Move 1: *removed = 2, size becomes 6, data[0] = data[6].
7 7 is the new root, too big
/ \
4 3
/ \ /
9 5 6
Move 2: heapify_down(heap, 0) takes over.
Children 4 and 3: 3 is smaller and 3 < 7, so swap index 0 with index 2.
3
/ \
4 7 7 sank to index 2
/ \ /
9 5 6
At index 2 the only child is 6, and 6 < 7, so swap index 2 with index 5.
3
/ \
4 6
/ \ /
9 5 7 7 sank to index 5, a leaf: stop
index: 0 1 2 3 4 5
value: 3 4 6 9 5 7Order matters inside your function. Save the root before anything overwrites it, and shrink size first so that heap->data[heap->size] is the old last value. Removing again and again hands the values back smallest first.
Requirements:
1. When heap_is_empty(heap) is true, return 0 and change nothing: leave *removed and the heap alone.
2. Otherwise copy heap->data[0] into *removed before anything overwrites it.
3. Shrink heap->size by one, move the old last value, heap->data[heap->size], into index 0, then call heapify_down(heap, 0).
4. Return 1 after a value is removed. Removing the only value leaves an empty heap with size 0.
5. Leave the MinHeap struct and every provided function as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 1 3 2 7 4 6 5 9 8 removed 1 MinHeap: 2 3 5 7 4 6 8 9 removed 2 MinHeap: 3 4 5 7 9 6 8
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...