CJCoding With Joseph
15free / daySign inCreate account

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 1

Change 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 0

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

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.