Understanding How to Check if an Array Represents a Max Heap

What is a Max Heap?

A Max Heap is a special type of binary tree that satisfies two conditions:

1. Complete Binary Tree

   • All levels are completely filled except possibly the last.

   • The last level is filled from left to right.

2. Heap Property (Max Heap Rule)

   • Every parent node is greater than or equal to its children.

In simple words:
The largest element is always at the root, and every parent is bigger than its children.

How is a Heap Stored in an Array?

Instead of using nodes and pointers, heaps are usually stored in arrays.

For any index i:

• Left child → 2*i + 1

• Right child → 2*i + 2

• Parent → (i - 1) / 2

Example

Valid Max Heap

Array: [90, 15, 10, 7, 12, 2]

Tree form:

        90
       /  \
     15    10
    /  \   /
   7   12 2

Every parent is greater than children → Valid Max Heap

Invalid Max Heap

Array: [9, 15, 10, 7, 12, 11]

Tree form:

        9
       / \
     15   10
    / \    \
   7  12   11

9 < 15 → Violates max heap property

Key Observation

You only need to check parent nodes, not all elements.

Why?
Because leaf nodes have no children, so they always satisfy the condition.

• Total nodes = n

• Last non-leaf node = (n / 2) - 1

Algorithm

1. Loop from i = 0 to (n/2) - 1

2. For each index:

   • Check left child

   • Check right child

3. If any child is greater than parent → return false

4. If all checks pass → return true

Java Implementation

class Solution {
    public boolean isMaxHeap(int[] arr) {
        int n = arr.length;

        for (int i = 0; i <= (n / 2) - 1; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < n && arr[i] < arr[left]) {
                return false;
            }

            if (right < n && arr[i] < arr[right]) {
                return false;
            }
        }

        return true;
    }
}

Complexity Analysis

• Time Complexity: O(n)
  (We check each parent once)

• Space Complexity: O(1)
  (No extra space used)

Why This Works Efficiently

• We avoid building a tree → saves time and space

• Direct index math makes checking fast

• Only half the array is processed

Common Mistakes to Avoid

Checking all nodes instead of only non-leaf nodes
Forgetting boundary checks (left < n, right < n)
Confusing min heap with max heap

Final Insight

Think of it like this:

“If every parent node dominates its children, the structure is a max heap.”