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:

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.

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

Why This Works Efficiently

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