CJCoding With Joseph
15free / daySign inCreate account

Pick the Smaller Child

Complete get_smaller_child_index. Given an index i, it returns the index of the child of i that holds the smaller value, or -1 when i has no children at all. Some heap code makes this pick inside the sinking loop (the C++ lesson's heapifyDown does). Here it gets its own function, so heapify_down stays short.

Reminder: why heapify down needs the smaller child. 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. When a value is too big for its slot, heapify down sinks it by swapping it with one of its children, and it has to be the SMALLER child: whichever child moves up becomes the parent of the other one, so it cannot be the bigger of the two. The left child of i is at 2 * i + 1 and the right child is at 2 * i + 2, but near the bottom of the tree one or both of them may be missing.

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

            1
          /   \
         4     3
        / \   / \
       5   6 7   7
      /
     9

index 0 holds 1: children 4 and 3, the 3 is smaller, return its index, 2
index 1 holds 4: children 5 and 6, the 5 is smaller, return its index, 3
index 2 holds 3: children 7 and 7, a tie, so return the left one, index 5
index 3 holds 5: only a left child, the 9, return its index, 7
indexes 4 to 7: no children, they are leaves, return -1

The answer is always an index, never a value: for index 1 the smaller child holds 5, but the function returns 3 because that is where the 5 sits. When the two children hold the same value, as under index 2, return the left one, so you only switch to the right child when it is strictly smaller.

Requirements: 1. Return -1 when i has no left child. A complete tree never has a right child without a left one, so such a node is a leaf. 2. Return the left child's index when i has a left child but no right child. 3. When both children exist, return the index of the one with the smaller value. Ties go to the left child: pick the right child only when its value is strictly smaller. 4. Check has_left_child and has_right_child before you read a child. Never read heap->data at an index of heap->size or more. 5. Do not change the heap. Leave the MinHeap struct and every provided function as they are.

Do NOT write a main function.

Expected Output:

MinHeap: 1 5 2 6 9 4 3 10 12 11
index 0 (1): left 5, right 2 -> returns 2 (value 2)
index 1 (5): left 6, right 9 -> returns 3 (value 6)
index 2 (2): left 4, right 3 -> returns 6 (value 3)
index 3 (6): left 10, right 12 -> returns 7 (value 10)
index 4 (9): left 11, right none -> returns 9 (value 11)
index 5 (4): left none, right none -> returns -1
index 6 (3): left none, right none -> returns -1
index 7 (10): left none, right none -> returns -1
index 8 (12): left none, right none -> returns -1
index 9 (11): left none, right none -> returns -1

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

Hints3 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.