☕ DSA Java Articles

Topics › Heaps › Learning

Check if an array represents a min heap

Medium TUF ID 571 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an integer array arr of length n. Read it as a complete binary tree stored level by level: the root is arr[0], and the children of arr[i] are arr[2i + 1] and arr[2i + 2] when those indices exist. Return true if this tree is a min heap, meaning every node is less than or equal to all of its descendants, and false otherwise.

Constraints: 0 ≤ n ≤ 10^5, values fit in an int, duplicates are allowed (a node may equal its child). The shape condition of a heap holds automatically, because an array has no gaps; only the order condition needs checking. The same question for a max heap is answered by flipping every comparison.

Example 1

arr = [10, 20, 30, 21, 23]
answer = true            // 10 <= 20, 30;  20 <= 21, 23;  30 has no children

Example 2

arr = [10, 20, 30, 25, 15]
answer = false           // 15 sits at index 4, a child of index 1, and 15 < 20

Approach 1: Brute force, straight from the definition

Intuition. The definition says “every node is at most everything below it”, so the literal check compares every node with every descendant. Enumerating a node’s descendants in an array heap is easy because they come in contiguous blocks: the children of i are indices [2i + 1, 2i + 2], the grandchildren are [4i + 3, 4i + 6], and in general if one level of the subtree occupies [lo, hi], the next occupies [2lo + 1, 2hi + 2]. So we can walk the subtree level by level with two numbers and no stack.

Algorithm.

  1. For every index i:
  2. Set lo = 2i + 1, hi = 2i + 2 (as long, so they cannot overflow).
  3. While lo < n: compare arr[i] with every arr[j] for j from lo to min(hi, n - 1); return false if some arr[j] < arr[i]. Then move to the next level: lo = 2lo + 1, hi = 2hi + 2.
  4. Return true when every node passes.
static boolean bruteForce(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        // the descendants of i on each level form one contiguous block of indices [lo, hi]
        long lo = 2L * i + 1, hi = 2L * i + 2;
        while (lo < n) {
            long last = Math.min(hi, n - 1);
            for (long j = lo; j <= last; j++) {
                if (arr[(int) j] < arr[i]) return false;
            }
            lo = 2 * lo + 1;
            hi = 2 * hi + 2;
        }
    }
    return true;
}

Complexity. Time O(n log n). Count the work from the other side: element j is compared once for every ancestor it has, and a complete tree has height floor(log2 n), so each element takes part in at most log2 n comparisons. Space O(1).

The work is wasted, though. If a <= b and b <= c, then a <= c comes for free. We should not need to compare a node with its grandchildren at all.

Approach 2: Recursive, parent against children

Intuition. By transitivity, a tree in which every parent is at most each of its children automatically has every node at most all of its descendants: follow the path from any node down to any descendant, and each step can only keep the value the same or increase it. So the heap property is equivalent to a local rule on each parent-child edge. A recursive formulation reads exactly like the definition of a heap: the tree rooted at i is a heap if i is not larger than its children and both child subtrees are heaps.

Algorithm.

  1. isHeapFrom(i): let l = 2i + 1, r = 2i + 2.
  2. If l >= n, node i is a leaf (or the array is empty): return true.
  3. If arr[l] < arr[i], or r < n and arr[r] < arr[i], return false.
  4. Return isHeapFrom(l) && isHeapFrom(r). When r >= n the second call returns true immediately, because 2r + 1 >= n too.
static boolean recursive(int[] arr) {
    return isHeapFrom(arr, 0);
}

static boolean isHeapFrom(int[] arr, int i) {
    int n = arr.length;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l >= n) return true;                              // a leaf, or the empty array
    if (arr[l] < arr[i]) return false;
    if (r < n && arr[r] < arr[i]) return false;
    return isHeapFrom(arr, l) && isHeapFrom(arr, r);      // isHeapFrom(arr, r) is true at once when r >= n
}

Complexity. Time O(n): each node is visited once and does constant work. Space O(log n) for the recursion stack, since the depth of a complete tree is floor(log2 n), only about 17 levels for 10^5 elements, so stack overflow is not a concern here.

Approach 3: Optimal, every child against its parent

Intuition. The recursion visits every edge once, but the array already lists every edge for us: each index i ≥ 1 has exactly one parent, (i - 1) / 2. So checking every edge is a single loop over the children. No recursion, no bookkeeping, and it stops at the first violation.

Algorithm.

  1. For i from 1 to n - 1: if arr[(i - 1) / 2] > arr[i], return false.
  2. Return true.
static boolean optimal(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[(i - 1) / 2] > arr[i]) return false;
    }
    return true;
}

Dry run on Example 2, arr = [10, 20, 30, 25, 15]:

i arr[i] parent index arr[parent] parent > child?
1 20 0 10 no
2 30 0 10 no
3 25 1 20 no
4 15 1 20 yes, return false

Complexity. Time O(n) with n - 1 comparisons in the worst case. Space O(1).

Equivalently you can loop over parents i from 0 to n / 2 - 1 (the internal nodes) and compare each with its one or two children. The child-to-parent loop is shorter because every non-root index has exactly one parent, so there is no “does the right child exist?” check.

Edge cases and pitfalls