Pick the Smaller Child
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 -1The 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.
Your Output
Run your code to see the output here...