Check Whether an Array Is a Min Heap
Check Whether an Array Is a Min Heap
Complete is_min_heap. It reads a plain array of count values as a tree and returns 1 when every child is greater than or equal to its parent, or 0 when at least one child is smaller than its parent.
Reminder: what makes an array 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, so any array can be drawn as a tree. What makes it a min heap is one rule: every parent is smaller than or equal to its children, so the smallest value is at index 0. For index i, the left child is at 2 * i + 1 and the right child is at 2 * i + 2. The rule only compares a parent with its own children. A min heap is NOT a binary search tree: nothing orders a left child against its right sibling, and values on different sides are never compared. In 1 7 2 8 9 4, the 7 just under the root is bigger than the 4 two rows down on the right side, and that is fine because the 7 is not the 4's parent.
values: 3 5 4 9 6 8 (count 6)
index: 0 1 2 3 4 5
value: 3 5 4 9 6 8
3 index 0: 3 <= 5 and 3 <= 4, fine
/ \
5 4 index 1: 5 <= 9 and 5 <= 6, fine
/ \ / index 2: 4 <= 8, no right child, fine
9 6 8 index 3, 4, 5: no children to check
no child is smaller: return 1Change one value and the answer flips. Here 2 sits under 5:
values: 3 5 4 9 2 8 (count 6)
index: 0 1 2 3 4 5
value: 3 5 4 9 2 8
3 index 0: 3 <= 5 and 3 <= 4, fine
/ \
5 4 index 1: 5 <= 9, but its right child,
/ \ / index 4, holds 2, and 2 < 5
9 2 8 a child is smaller than its parent: return 0So the function is one walk over the array. At each index, ask the helpers where the two children are, skip a child whose index is count or more, and compare the rest with the parent. A single bad pair is enough to return 0, and only an array where every pair passes earns a 1.
Requirements:
1. is_min_heap(values, count) returns 1 when every existing child is greater than or equal to its parent, and 0 when at least one child is smaller than its parent.
2. A child exists only when its index is less than count. Never read values[count] or anything past it.
3. Equal values are fine: a child equal to its parent does not break the rule.
4. An empty array (count 0) and an array of one value are both min heaps, so return 1 for them.
5. Only a parent and its own children are compared. A left child bigger than its right sibling, or a value bigger than one lower down on the other side (like the 7 and the 4 in the reminder), still makes a min heap.
6. Use get_left_child_index and get_right_child_index for the index math, leave them as they are, and do not change values.
Do NOT write a main function.
Expected Output:
[] min heap: yes [7] min heap: yes [4 4 4 4] min heap: yes [1 8 2 9 10 3] min heap: yes [2 9 5] min heap: yes [1 5 6] min heap: yes
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...