☕ DSA Java Articles

Topics › Heaps › Learning

Convert Min Heap to Max Heap

Medium TUF ID 572 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr of n integers that represents a min heap (every element is at most its children 2i + 1 and 2i + 2). Rearrange the elements in place so that the array represents a max heap: every element is at least its children.

Constraints: 0 ≤ n ≤ 10^5, values fit in an int, duplicates are allowed. Many arrangements are valid max heaps; judges usually expect the arrangement produced by bottom-up heapify (Approach 3), which is also what the examples show. The Java tests accept any valid max heap with the same elements, and additionally pin the exact layouts quoted below.

Example 1

arr = [1, 2, 3, 4]
answer = [4, 2, 3, 1]                    // 4 >= 2, 3;  2 >= 1

Example 2

arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
answer = [20, 18, 10, 12, 9, 9, 3, 5, 6, 8]

The key observation before any code: the fact that the input is a min heap does not help. A min heap is “nearly sorted the wrong way round”, so the task is really build a max heap from an arbitrary array. All three approaches below work for any input, and the tests feed them both min heaps and plain arrays.

Approach 1: Brute force, sort descending

Intuition. A parent always has a smaller index than its children. So if the array is sorted in non-increasing order, every parent is automatically at least its children: the max-heap property holds trivially. Sorting does far more work than needed, since a heap only requires order along parent-child edges, but it is impossible to get wrong.

Algorithm.

  1. Sort the array ascending.
  2. Reverse it with two pointers.
static void bruteForce(int[] arr) {
    Arrays.sort(arr);
    for (int i = 0, j = arr.length - 1; i < j; i++, j--) swap(arr, i, j);
}

Complexity. Time O(n log n) for the sort. Space O(log n) at most for the library’s sort of primitives; the reversal is in place.

Approach 2: Better, insert one by one (top-down build)

Intuition. A max heap can be grown in place. Treat the prefix arr[0..k-1] as a max heap that is already correct; then “insert” arr[k], which is already sitting in the next free slot, by sifting it up: while it is larger than its parent, swap them. After processing every k, the whole array is a max heap. This is exactly the insert operation of a heap, applied n - 1 times.

Algorithm.

  1. For k from 1 to n - 1:
  2. Set i = k. While i > 0 and arr[parent(i)] < arr[i], swap them and move i to the parent.
static void better(int[] arr) {
    for (int k = 1; k < arr.length; k++) {
        int i = k;
        while (i > 0 && arr[(i - 1) / 2] < arr[i]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
}

Complexity. Time O(n log n): a sift-up can climb the full height log2 n, and about half the nodes are leaves at the bottom level. On a min heap input this is close to the worst case, because larger values tend to sit near the end of the array and each one climbs a long way. Space O(1).

Approach 3: Optimal, bottom-up heapify

Intuition. Turn the build around. Every leaf (indices n / 2 to n - 1) is already a one-element max heap. Now process internal nodes from the last one, n / 2 - 1, back to the root. When we reach node i, both of its subtrees are already max heaps, and the only possible problem is node i itself being smaller than a child. Sifting it down (swap with the larger child while that child is bigger) fixes the subtree rooted at i. When the loop reaches the root, the whole array is a max heap.

Why is this cheaper than Approach 2? Sift-down costs at most the node’s height, and heights are small for most nodes: half the nodes have height 0 and are skipped, a quarter have height at most 1, an eighth at most 2, and so on. The total work is n × (1/4 + 2/8 + 3/16 + ...), which is at most n. Sift-up, in contrast, costs the node’s depth, which is large for most nodes.

Algorithm.

  1. For i from n / 2 - 1 down to 0, call siftDown(arr, n, i).
  2. siftDown: find largest among i, 2i + 1, 2i + 2 (only indices below n). If it is i, stop. Otherwise swap arr[i] with arr[largest] and continue from largest.
static void optimal(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, n, i);
}

static void siftDown(int[] arr, int n, int i) {
    while (true) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest == i) return;
        swap(arr, i, largest);
        i = largest;
    }
}

static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

Dry run on arr = [10, 20, 30, 21, 23] (n = 5, internal nodes 1 and 0):

step node children larger child array after
1 i = 1 (20) 21, 23 23 at index 4 [10, 23, 30, 21, 20]
2 index 4 none stop [10, 23, 30, 21, 20]
3 i = 0 (10) 23, 30 30 at index 2 [30, 23, 10, 21, 20]
4 index 2 none (5, 6 ≥ n) stop [30, 23, 10, 21, 20]

For comparison, Approach 2 turns the same array into [30, 23, 20, 10, 21] and Approach 1 into [30, 23, 21, 20, 10]. All three are valid max heaps.

Complexity. Time O(n) by the height argument above. Space O(1): the sift-down is iterative.

Edge cases and pitfalls