Min-Heap Array Check
Problem
A list of numbers can be read as a binary tree: the value at index i has its children at indexes 2i + 1 and 2i + 2, when those exist. Decide whether the list already satisfies the min-heap rule, meaning no value is larger than either of its children. Return True if it does and False otherwise. An empty list or a single value counts as a valid heap.
Examples
Input: values = [1, 3, 2, 7, 4]
Output: True
Why: 1 sits above 3 and 2, and 3 sits above 7 and 4Input: values = [2, 1, 3]
Output: False
Why: the root 2 is larger than its left child 1Input: values = [5, 5, 5]
Output: True
Why: edge case, equal values never break the ruleHints
0 / 3
You never need to build a tree. The index arithmetic already tells you who is the parent of whom.
If every parent is no larger than its own children, the rule holds all the way down, because smaller-or-equal chains together.
Walk every index from 1 to the end, find its parent at (i - 1) // 2, and fail as soon as a parent is larger than the child. If the walk finishes, the list is a heap.
Solution
The heap rule is local: if each parent is no larger than its children, then every ancestor is no larger than every descendant, because the comparisons chain. So it is enough to check each non-root index against its parent, which lives at (i - 1) // 2. Checking from the child side visits every parent-child pair exactly once. Time is O(n) and space is O(1).
def is_min_heap(values):
for child in range(1, len(values)):
parent = (child - 1) // 2 # the array position of this value's parent
if values[parent] > values[child]:
return False # one broken pair is enough to fail
return True
print(is_min_heap([1, 3, 2, 7, 4])) # -> True
print(is_min_heap([2, 1, 3])) # -> False
print(is_min_heap([5, 5, 5])) # -> TrueStuck on the idea rather than the code? Heapify and Sift covers it.