Check That Every Value Is at Least Its Parent
Check That Every Value Is at Least Its Parent
Complete min_heap_valid. It returns true when the values in the array really form a min heap, and false when at least one value is smaller than its parent. The lab uses it to test the other functions.
Reminder: how this min heap is stored. A min_heap is a struct with three fields: capacity (the most values it can hold), count (how many it holds now) and values (a pointer to an array made with malloc). The heap is a complete binary tree kept in that array, filled row by row with no gaps, so only slots 0 to count - 1 are in use. Every parent is smaller than or equal to its children, so the smallest value is always at index 0. For the value at index i, the parent is at (i - 1) / 2 and the children are at 2 * i + 1 and 2 * i + 2.
The rule is only between a child and its OWN parent. Two siblings can be in any order, and a value on the left side can be bigger than one on the right side.
valid not valid
1 1
/ \ / \
8 2 8 > 2 is fine: 8 2
/ \ they are siblings / \
9 8 9 5 <- 5 is smaller than its parent 8
1 8 2 9 8 1 8 2 9 5
^ index 4, its parent is index (4 - 1) / 2 = 1Every slot except index 0 has a parent, so the check is: walk the slots from index 1 to the end, and compare each one with the slot at (i - 1) / 2.
Requirements:
1. Return false as soon as you find a value that is smaller than its parent.
2. Return true when no value is smaller than its parent. Equal values are allowed.
3. An empty heap and a heap of one value are valid.
4. Do not change the heap.
Do NOT write a main function.
Expected Output:
1 8 2 9 8: valid yes 1 8 2 9 5: valid no
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...