Find a Heap Node's Parent and Children
Find a Heap Node's Parent and Children
Complete the three index helpers get_parent_index, get_left_child_index and get_right_child_index. Each one takes the index of a node in the heap array and returns the index of one of its relatives.
Reminder: how a min heap lives in an array. A min heap is a complete binary tree: every row is full except maybe the last one, and the last row fills from left to right with no gaps. Because there are no gaps, the whole tree fits in a plain array with no pointers at all. The root sits at index 0, its two children at 1 and 2, their children at 3, 4, 5 and 6, and so on, row by row. In a min heap every parent is smaller than or equal to its children, so the smallest value is always at index 0.
index: 0 1 2 3 4 5
value: 2 6 3 11 8 4
2 row 0: index 0
/ \
6 3 row 1: index 1, 2
/ \ /
11 8 4 row 2: index 3, 4, 5
the same tree with each node's index in place of its value
0
/ \
1 2
/ \ / \
3 4 5 6 <- index 6 is not in use yet: the next value would go hereRead the pattern off the index tree. Index 1 has children 3 and 4, and index 2 has its left child at 5 (its right child would be index 6, one slot past the end of this heap), so every step down a row roughly doubles the index. Going up is the same trip backwards, and because integer division drops the remainder, both children of a node lead back to the same parent.
Requirements:
1. get_left_child_index(i) and get_right_child_index(i) return the indexes of the two children of index i: index 0 has children 1 and 2, index 1 has children 3 and 4, index 2 has children 5 and 6.
2. get_parent_index(i) returns the index directly above i: indexes 1 and 2 lead to 0, indexes 3 and 4 lead to 1, indexes 5 and 6 lead to 2. It is only called with i greater than 0, because the root has no parent.
3. A child index can land past the end of the heap. describe already compares it with heap->size before it reads the array, so your helpers only do the arithmetic.
4. Leave the MinHeap struct, heap_load, describe and heap_print as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 10 40 20 70 50 30 children of 0: 1 2 children of 2: 5 6 parent of 4: 1 parent of 5: 2 index 1 (40): parent index 0 (10), left index 3 (70), right index 4 (50) index 2 (20): parent index 0 (10), left index 5 (30), right none
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...