CJCoding With Joseph
15free / daySign inCreate account

Write heapify_down From Scratch

Complete heapify_down(MinHeap *heap, int i). The value at index i may be bigger than one of its children, and your loop sinks it down the tree, one swap at a time, until the heap rule holds again. It returns nothing: it rearranges heap->data in place. In the easy question, Sink a Value Down With heapify_down, the provided get_smaller_child_index picked the child for you. That helper is not in this file, so here you pick the smaller child yourself with has_left_child, has_right_child and the index helpers.

Reminder: how a value sinks 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. For index i the left child is at 2 * i + 1 and the right child at 2 * i + 2, and has_left_child and has_right_child tell you whether those slots are inside the heap. Remove moves the last value to the root, and that value is usually too big for the top, so heapify down sinks it by swapping it with its SMALLER child, again and again.

9 was just written into index 0, over the old root. Everything below it is still in heap order:

index:   0   1   2   3   4   5   6
value:   9   4   3   8   5   6   7

            9           i = 0: children hold 4 and 3, take index 2
          /   \
         4     3
        / \   / \
       8   5 6   7

step 1: 3 < 9, so swap index 0 and index 2

            3
          /   \
         4     9        i = 2: children hold 6 and 7, take index 5
        / \   / \
       8   5 6   7

step 2: 6 < 9, so swap index 2 and index 5

            3
          /   \
         4     6
        / \   / \
       8   5 9   7      i = 5: no children, so stop

index:   0   1   2   3   4   5   6
value:   3   4   6   8   5   9   7

Each pass of the loop looks at the children of the slot the value is on, picks the smaller one, and swaps only when that child is smaller than the value. It has to be the SMALLER child: the child that moves up becomes the parent of its old sibling, so it must not be bigger than that sibling. The trip ends when the value is no bigger than its smaller child, or when it reaches a slot with no children.

Requirements: 1. heapify_down(heap, i) starts at index i and only moves values from i downward. Slots above i are left alone. 2. At each step find the smaller child: the left child, unless a right child exists and holds a strictly smaller value, so a tie goes to the left child. get_smaller_child_index is not in this file, so use has_left_child, has_right_child and the index helpers. 3. Swap with that child (use swap) only when the child is strictly smaller than the value at i, then carry on from the child's index. 4. Stop when the value at i is smaller than or equal to its smaller child, or when i has no left child. Because the tree fills from the left, a slot with no left child is a leaf. 5. A slot with only a left child still has to be checked against that one child. 6. Leave the other functions as they are.

Do NOT write a main function.

Expected Output:

MinHeap: 1 2 5 4 3 8 6 9 7 11 10
index 0 set to 20
MinHeap: 20 2 5 4 3 8 6 9 7 11 10
after heapify_down(0)
MinHeap: 2 3 5 4 10 8 6 9 7 11 20
20 is now at index 10

= newline. The output ends with a newline — print one after the last line.

Hints4 available
Topics:
Data Structures & AlgorithmsHeaps
1
Tab to indent (Esc then Tab to move on) · Ctrl+Enter to run · Shift+Alt+F to format · Ctrl+Space to expand shortcuts (p, fori)

Your Output

Run your code to see the output here...

Test Cases

Run your code to see test case results.