Convert a Max Heap to a Min Heap

You're given an array that represents a max-heap (every parent >= its children). Rearrange it in place so that it represents a valid min-heap: for every index i, a[i] <= a[2i + 1] and a[i] <= a[2i + 2], wherever those children exist.

Example

Input:  [9, 4, 7, 1, -2, 6, 5]
Output: [-2, 1, 5, 9, 4, 6, 7]    (any valid min-heap is accepted)

graph TB
    subgraph maxh["input: max-heap"]
        a0["9"] --> a1["4"]
        a0 --> a2["7"]
        a1 --> a3["1"]
        a1 --> a4["-2"]
        a2 --> a5["6"]
        a2 --> a6["5"]
    end
    subgraph minh["output: min-heap"]
        b0["-2"] --> b1["1"]
        b0 --> b2["5"]
        b1 --> b3["9"]
        b1 --> b4["4"]
        b2 --> b5["6"]
        b2 --> b6["7"]
    end

Brute force: sort the array

A sorted array is always a valid min-heap: every parent's index is smaller than its children's indices, so in ascending order every parent is <= its children.

import java.util.Arrays;

public class Main {
    static void toMinHeap(int[] heap) {
        Arrays.sort(heap);
    }

    static boolean isMinHeap(int[] heap) {
        for (int i = 1; i < heap.length; i++) {
            if (heap[(i - 1) / 2] > heap[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] heap = {9, 4, 7, 1, -2, 6, 5};
        toMinHeap(heap);
        System.out.println(Arrays.toString(heap) + " valid = " + isMinHeap(heap));
    }
}

[-2, 1, 4, 5, 6, 7, 9] valid = true

Time: O(n log n). Space: O(1) extra for the data (Arrays.sort on an int[] sorts in place; it uses a small amount of stack space). Sorting does more than needed: a heap only has to be partially ordered.

Optimal: bottom-up heapify

The fact that the input was a max-heap doesn't help, so treat it as an arbitrary array and build a min-heap from it.

siftDown(i) fixes the heap rule at index i, assuming both subtrees below i are already valid min-heaps: while the value at i is larger than its smaller child, swap them and continue from the child's position.

Heapify calls siftDown on every parent, starting from the last one (index n/2 - 1) and moving backwards to the root. Leaves (indices n/2 to n - 1) are already valid one-element heaps. Going backwards means that when a node is processed, both of its subtrees have already been fixed.

Walkthrough with [9, 4, 7, 1, -2, 6, 5] (n = 7, parents are indices 2, 1, 0):

import java.util.Arrays;

public class Main {
    static void siftDown(int[] heap, int i) {
        int n = heap.length;
        while (true) {
            int left = 2 * i + 1, right = 2 * i + 2;
            int smallest = i;
            if (left < n && heap[left] < heap[smallest]) smallest = left;
            if (right < n && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) return; // the heap rule holds here
            int t = heap[i];
            heap[i] = heap[smallest];
            heap[smallest] = t;
            i = smallest;
        }
    }

    static void toMinHeap(int[] heap) {
        for (int i = heap.length / 2 - 1; i >= 0; i--) {
            siftDown(heap, i);
        }
    }

    static boolean isMinHeap(int[] heap) {
        for (int i = 1; i < heap.length; i++) {
            if (heap[(i - 1) / 2] > heap[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] heap = {9, 4, 7, 1, -2, 6, 5};
        toMinHeap(heap);
        System.out.println(Arrays.toString(heap) + " valid = " + isMinHeap(heap));

        int[] empty = {};
        toMinHeap(empty);
        System.out.println(Arrays.toString(empty));

        int[] dups = {3, 3, 3, 1, 1};
        toMinHeap(dups);
        System.out.println(Arrays.toString(dups) + " valid = " + isMinHeap(dups));
    }
}

[-2, 1, 5, 9, 4, 6, 7] valid = true
[]
[1, 1, 3, 3, 3] valid = true

Time: O(n). Space: O(1).

Why heapify is O(n), not O(n log n)

A node can only sift down as far as its height above the bottom of the tree. Half the nodes are leaves and don't move at all. A quarter can move one level, an eighth two levels, and so on. The total is n/4·1 + n/8·2 + n/16·3 + ..., which adds up to less than n. Only the root can move log n levels.

The loop from heap.length / 2 - 1 down to 0 visits exactly the parents, from last to first. When n is 0 or 1 the start index is -1, so the loop body never runs. The PriorityQueue constructor that takes a collection also builds its heap bottom-up in O(n).

Edge cases

• Empty array or one element: already a min-heap.
• Duplicates: allowed, since the rule uses <=.
• Min-heap to max-heap: the same code with > in place of <.