Sink a Value Down With heapify_down
Sink a Value Down With heapify_down
Complete heapify_down. It takes the index of a value that may be bigger than one of its children and moves that value down the tree, one swap at a time, until the min heap rule holds again. It returns nothing: it rearranges heap->data in place.
Reminder: why a value has to sink down. 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 moves the last value into the root, where it is usually too big. It sinks by swapping with its SMALLER child, the one the provided get_smaller_child_index picks: the child that moves up becomes the parent of its old sibling, so it has to be the smaller of the two. This is heapify up turned upside down: the same kind of loop, walking away from the root instead of toward it.
Here the root holds 6, which is too big for it. Everything below the root is in heap order:
Start: i = 0. The children of index 0 hold 1 and 3, so
get_smaller_child_index(heap, 0) returns index 1.
6 <- moving value, index 0
/ \
1 3 <- smaller child: the 1 at index 1
/ \ / \
2 5 4 8
/ \
9 7
Step 1: 1 < 6, so swap index 0 with index 1. Now i = 1.
Its children hold 2 and 5, so the smaller child is index 3.
1
/ \
6 3 <- moving value, index 1
/ \ / \
2 5 4 8 <- smaller child: the 2 at index 3
/ \
9 7
Step 2: 2 < 6, so swap index 1 with index 3. Now i = 3.
Its children hold 9 and 7, so the smaller child is index 8.
1
/ \
2 3
/ \ / \
6 5 4 8 <- moving value, index 3
/ \
9 7 <- smaller child: the 7 at index 8
Step 3: 7 is not smaller than 6, so the loop stops. 6 is in place.
index: 0 1 2 3 4 5 6 7 8
before: 6 1 3 2 5 4 8 9 7
after: 1 2 3 6 5 4 8 9 7The loop has two ways to end. One is step 3: the smaller child is not smaller than the moving value, so the value is in place, and an equal child does not swap either. The other is a leaf: there is no child at all, and get_smaller_child_index returns -1. If the root had held 10 instead of 6, step 3 would swap it with the 7, and it would stop at index 8, a leaf.
Requirements:
1. heapify_down(heap, i) swaps the value at index i with its smaller child while that child exists and holds a strictly smaller value. After each swap, i becomes the child's index.
2. Ask the provided get_smaller_child_index for the child again every time i changes. It returns -1 when i has no children, and it already sends ties to the left child.
3. Stop when there is no child (-1) or when the smaller child is greater than or equal to the value. Equal values do not swap, and heap->data[-1] is never read.
4. Use swap. Only values on the path from i down to where the value stops move: slots above i, the other side of the tree and heap->size do not change.
5. Leave the MinHeap struct and the provided functions (heap_load, the index helpers, has_left_child, has_right_child, swap, get_smaller_child_index, heap_print) as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 1 5 2 6 8 3 9 10 7 11 12 14 4 13 15 put 20 at index 0 MinHeap: 20 5 2 6 8 3 9 10 7 11 12 14 4 13 15 heapify_down from index 0 MinHeap: 2 5 3 6 8 4 9 10 7 11 12 14 20 13 15 put 16 at index 1 MinHeap: 2 16 3 6 8 4 9 10 7 11 12 14 20 13 15 heapify_down from index 1 MinHeap: 2 6 3 7 8 4 9 10 16 11 12 14 20 13 15
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...