Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Validate Heap Property in Array

MEDIUMProblemSolveExternal Links

Description

Given an array of size n, determine whether it represents a valid level-order representation of a Max-Heap.

In a max-heap stored as an array, the element at any index i must be greater than or equal to the elements at indices 2i+1 (left child) and 2i+2 (right child), provided those children exist within the array bounds.

Return 1 (true) if the array satisfies the max-heap property for every node, or 0 (false) if any node violates it.

Examples

Example 1

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

Output: 1 (True)

Explanation: The array represents the following complete binary tree:

       90
      /    \
    15      10
   /  \    /
  7   12  2

Every parent node is greater than or equal to its children:

  • 90 ≥ 15 and 90 ≥ 10
  • 15 ≥ 7 and 15 ≥ 12
  • 10 ≥ 2

The tree satisfies the max-heap property at every node.

Example 2

Input: n = 6, arr = [9, 15, 10, 7, 12, 11]

Output: 0 (False)

Explanation: The array represents this tree:

       9
      /    \
    15      10
   /  \    /
  7   12  11

Multiple violations exist:

  • Root 9 < left child 15 (violation)
  • Root 9 < right child 10 (violation — though 9 is NOT ≥ 10 only matters as a max-heap check)
  • Node 10 < child 11 (violation)

Since the root is smaller than its children, the max-heap property is violated.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

The max-heap property states that every node must be greater than or equal to ALL of its descendants — not just its direct children, but grandchildren, great-grandchildren, and so on.

The most direct way to verify this is to take each node and walk up through all its ancestors (parent, grandparent, great-grandparent, etc.) all the way to the root, checking that every ancestor is ≥ the current node.

Think of it like a corporate hierarchy where every manager must earn more than everyone below them. The brute force approach is to take each employee and personally verify their salary against every single boss above them in the chain — all the way up to the CEO. This works, but it involves checking the same relationships multiple times. If we already confirmed that a middle manager earns more than a junior employee, we don't also need to separately confirm that the CEO earns more than that same junior.

Step-by-Step Explanation

Let's trace through Example 1: arr = [90, 15, 10, 7, 12, 2]

Step 1: Check node j=1 (value 15)

  • Parent at index 0 (value 90). Is 90 ≥ 15? YES ✓
  • Reached root. Node 1 passes.

Step 2: Check node j=2 (value 10)

  • Parent at index 0 (value 90). Is 90 ≥ 10? YES ✓
  • Reached root. Node 2 passes.

Step 3: Check node j=3 (value 7) — parent

  • Parent at index 1 (value 15). Is 15 ≥ 7? YES ✓
  • Continue walking up to grandparent.

Step 4: Check node j=3 — grandparent

  • Grandparent at index 0 (value 90). Is 90 ≥ 7? YES ✓
  • Reached root. Node 3 passes. Notice: this grandparent check was redundant.

Step 5: Check node j=4 (value 12) — parent

  • Parent at index 1 (value 15). Is 15 ≥ 12? YES ✓
  • Continue to grandparent.

Step 6: Check node j=4 — grandparent

  • Grandparent at index 0 (value 90). Is 90 ≥ 12? YES ✓
  • Reached root. Node 4 passes. Another redundant grandparent check.

Step 7: Check node j=5 (value 2) — parent

  • Parent at index 2 (value 10). Is 10 ≥ 2? YES ✓
  • Continue to grandparent.

Step 8: Check node j=5 — grandparent

  • Grandparent at index 0 (value 90). Is 90 ≥ 2? YES ✓
  • Reached root. Node 5 passes.

Step 9: Result

  • All nodes verified against all ancestors. Total: 8 comparisons.
  • Array IS a valid max-heap. Return True.
  • For Example 2 [9, 15, 10, 7, 12, 11], node j=1 (value 15) would fail at parent (9 < 15), returning False immediately.

Brute Force — Walking Up All Ancestor Paths — For each node, walk up through ALL ancestors to the root verifying the max-heap property. Notice the redundant grandparent checks that the optimal approach eliminates.

Algorithm

  1. For each node j from index 1 to n-1:
    a. Set ancestor = parent of j = (j - 1) / 2
    b. While ancestor ≥ 0:
    • If arr[ancestor] < arr[j], return False (violation found)
    • If ancestor is 0 (root reached), stop walking up
    • Otherwise, move ancestor to its parent: ancestor = (ancestor - 1) / 2
  2. If no violation was found, return True

Code

class Solution {
public:
    bool isMaxHeap(int arr[], int n) {
        // For each node, walk up through all ancestors
        for (int j = 1; j < n; j++) {
            int ancestor = (j - 1) / 2;
            while (ancestor >= 0) {
                // If any ancestor is smaller, heap property violated
                if (arr[ancestor] < arr[j]) {
                    return false;
                }
                // Stop when we reach root
                if (ancestor == 0) break;
                // Move to the next ancestor up
                ancestor = (ancestor - 1) / 2;
            }
        }
        return true;
    }
};
class Solution:
    def isMaxHeap(self, arr, n):
        # For each node, walk up through all ancestors
        for j in range(1, n):
            ancestor = (j - 1) // 2
            while ancestor >= 0:
                # If any ancestor is smaller, heap property violated
                if arr[ancestor] < arr[j]:
                    return False
                # Stop when we reach root
                if ancestor == 0:
                    break
                # Move to the next ancestor up
                ancestor = (ancestor - 1) // 2
        return True
class Solution {
    boolean isMaxHeap(int arr[], int n) {
        // For each node, walk up through all ancestors
        for (int j = 1; j < n; j++) {
            int ancestor = (j - 1) / 2;
            while (ancestor >= 0) {
                // If any ancestor is smaller, heap property violated
                if (arr[ancestor] < arr[j]) {
                    return false;
                }
                // Stop when we reach root
                if (ancestor == 0) break;
                // Move to the next ancestor up
                ancestor = (ancestor - 1) / 2;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

For each of the n-1 non-root nodes, we walk up to the root through all ancestors. The height of a complete binary tree with n nodes is ⌊log₂(n)⌋, so each node's ancestor walk takes at most O(log n) steps. Total comparisons: (n-1) × O(log n) = O(n log n).

Space Complexity: O(1)

We only use a few integer variables (j, ancestor). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force performs O(n log n) comparisons because it checks each node against ALL its ancestors, not just its direct parent. Many of these checks are redundant.

Consider node 7 (at index 3) in Example 1. The brute force verifies:

  • 15 ≥ 7 (parent check) ✓
  • 90 ≥ 7 (grandparent check) ✓

But the grandparent check is unnecessary. Since we already know 90 ≥ 15 (from checking node 15) and 15 ≥ 7, by the transitive property of ≥, we automatically know 90 ≥ 7. Checking it again is wasted work.

Key Insight: The heap property is transitive. If every parent ≥ its direct children, then by extension, every ancestor ≥ all its descendants. We only need to verify the n parent-child relationships — not the O(n log n) ancestor-descendant ones.

This reduces the problem from checking every ancestor path to checking only each parent against its immediate children — cutting the work from O(n log n) to O(n).

Optimal Approach - Iterative Parent-Child Check

Intuition

Instead of checking every ancestor-descendant relationship, we exploit a fundamental mathematical property: transitivity.

If A ≥ B and B ≥ C, then A ≥ C. This means that if every parent is ≥ its direct children, then by chaining these relationships, every ancestor is automatically ≥ all its descendants.

So we only need to verify the direct parent-child relationships — one check per edge in the tree. In a complete binary tree with n nodes, there are exactly n-1 edges (each non-root node has one parent). But we can organize the loop more naturally: iterate through all internal nodes (nodes that have at least one child) and check each against its children.

The last internal node in a complete binary tree stored as an array is at index ⌊(n-2)/2⌋. So we loop from index 0 to ⌊(n-2)/2⌋ and for each node, verify it is ≥ both its left child (at 2i+1) and right child (at 2i+2, if it exists).

This single pass through the internal nodes gives us O(n) time and O(1) space — the most efficient possible solution.

Side-by-side comparison: brute force checks all ancestor paths (8 comparisons) vs optimal checks only parent-child edges (5 comparisons), with transitivity explanation
Side-by-side comparison: brute force checks all ancestor paths (8 comparisons) vs optimal checks only parent-child edges (5 comparisons), with transitivity explanation

Step-by-Step Explanation

Let's trace through Example 1: arr = [90, 15, 10, 7, 12, 2], n = 6

The last internal node is at index ⌊(6-2)/2⌋ = 2. So we check nodes 0, 1, and 2.

Step 1: Check node 0 (value 90) — left child

  • Left child at index 1 (value 15). Is 90 ≥ 15? YES ✓

Step 2: Check node 0 (value 90) — right child

  • Right child at index 2 (value 10). Is 90 ≥ 10? YES ✓
  • Node 0 is valid.

Step 3: Check node 1 (value 15) — left child

  • Left child at index 3 (value 7). Is 15 ≥ 7? YES ✓

Step 4: Check node 1 (value 15) — right child

  • Right child at index 4 (value 12). Is 15 ≥ 12? YES ✓
  • Node 1 is valid.

Step 5: Check node 2 (value 10) — left child

  • Left child at index 5 (value 2). Is 10 ≥ 2? YES ✓

Step 6: Check node 2 (value 10) — right child

  • Right child would be at index 6, but n=6, so index 6 is out of bounds. No right child exists.
  • Node 2 is valid.

Step 7: Result

  • All internal nodes verified. Only 5 comparisons needed (vs 8 in brute force).
  • Array IS a valid max-heap. Return True.

For Example 2 [9, 15, 10, 7, 12, 11]: node 0 (value 9) vs left child (value 15) → 9 < 15, immediate False.

Optimal — Iterative Parent-Child Verification — Iterate through internal nodes only, checking each against its direct children. Transitivity guarantees this is sufficient to validate the entire heap.

Algorithm

  1. Calculate the last internal node index: lastInternal = (n - 2) / 2
  2. For each index i from 0 to lastInternal:
    a. Compute left = 2 * i + 1, right = 2 * i + 2
    b. If left < n and arr[i] < arr[left], return False
    c. If right < n and arr[i] < arr[right], return False
  3. If no violation found, return True

Code

class Solution {
public:
    bool isMaxHeap(int arr[], int n) {
        // Check only internal nodes against their direct children
        for (int i = 0; i <= (n - 2) / 2; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            // Left child must not exceed parent
            if (left < n && arr[i] < arr[left]) {
                return false;
            }
            // Right child must not exceed parent
            if (right < n && arr[i] < arr[right]) {
                return false;
            }
        }
        return true;
    }
};
class Solution:
    def isMaxHeap(self, arr, n):
        # Check only internal nodes against their direct children
        for i in range((n - 2) // 2 + 1):
            left = 2 * i + 1
            right = 2 * i + 2

            # Left child must not exceed parent
            if left < n and arr[i] < arr[left]:
                return False
            # Right child must not exceed parent
            if right < n and arr[i] < arr[right]:
                return False

        return True
class Solution {
    boolean isMaxHeap(int arr[], int n) {
        // Check only internal nodes against their direct children
        for (int i = 0; i <= (n - 2) / 2; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            // Left child must not exceed parent
            if (left < n && arr[i] < arr[left]) {
                return false;
            }
            // Right child must not exceed parent
            if (right < n && arr[i] < arr[right]) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the internal nodes of the tree, from index 0 to ⌊(n-2)/2⌋. The number of internal nodes in a complete binary tree is roughly n/2. For each internal node, we perform at most 2 comparisons (left and right child). Total comparisons: at most 2 × n/2 = n, giving O(n).

In the best case (early violation), we return False after just 1-2 comparisons. In the worst case (valid heap), we check all internal nodes.

Space Complexity: O(1)

We use only a few integer variables (i, left, right). No additional data structures, no recursion stack. This is the most space-efficient approach possible.