Check if an Array is Max Heap

Time: O(n)

Space: O(1)

Intuition

In a max heap stored as a 0-indexed array, every node at index i has its parent at (i-1)/2. The heap property requires every child to be ≤ its parent. Scanning children (not parents) is cleaner because every non-root node has exactly one parent — no edge case for nodes with only one child.

Algorithm

1Loop i from n-1 down to 1 (all non-root indices).
2For each i, compute parent = (i-1)/2.
3If arr[i] > arr[parent], return false immediately.
4If the loop completes without violation, return true.

Example Walkthrough

Input: arr = [90, 15, 10, 7, 12, 2]

1.i=5: arr[5]=2 <= arr[2]=10 ✓
2.i=4: arr[4]=12 <= arr[1]=15 ✓
3.i=3: arr[3]=7 <= arr[1]=15 ✓
4.i=2: arr[2]=10 <= arr[0]=90 ✓
5.i=1: arr[1]=15 <= arr[0]=90 ✓

Output: true

Common Pitfalls

•Do not start loop at i=0 — the root has no parent and (0-1)/2 gives an incorrect index.
•Use (i-1)/2 for 0-based indexing; do not use i/2.

Check if an Array is Max Heap.java

Java

// Approach: For every non-root node i, check arr[i] <= arr[(i-1)/2] (its parent).
// Iterating over children avoids the one-child edge case — parent index is always valid.
// Time: O(n) Space: O(1)
class Solution {

    public boolean isMaxHeap(int[] arr) {
        for (int i = arr.length - 1; i >= 1; i--) {
            if (arr[i] > arr[(i - 1) / 2]) {
                return false;
            }
        }

        return true;
    }
}

Was this solution helpful?