Convert min heap to max heap

The problem, simply

You get an array that is a min heap: every parent is smaller than or equal to its children. Rearrange it into a max heap: every parent bigger than or equal to its children. Return the array.

For [1, 2, 3, 6, 7, 8] one correct answer is [8, 7, 3, 6, 2, 1].

A story to remember it

Picture it

Examples

Way 1: the simple way

Sort the array from big to small. A sorted array always follows the max heap rule, because every parent sits earlier than its children and so is at least as big.

1. Sort the array.
2. Reverse it.

import java.util.Arrays;

class Solution {
    public void convertMinToMax(int[] a) {
        Arrays.sort(a);                                   // small to big
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            int t = a[i]; a[i] = a[j]; a[j] = t;          // now big to small
        }
    }
}

How long it takes: sorting is O(n log n). Extra room: Java sorts int arrays with a quicksort that uses O(log n) stack. It works, but it does more work than needed.

Way 2: the clever way

Treat the array as any random array and build a max heap from the bottom up.

1. Leaves (the second half of the array) have no children, so they are fine already.
2. For i from n / 2 - 1 down to 0, sift a[i] down: while a child is bigger, swap with the bigger child.

class Solution {
    public void convertMinToMax(int[] a) {
        int n = a.length;
        for (int i = n / 2 - 1; i >= 0; i--) {   // last parent back to the root
            siftDown(a, n, i);
        }
    }

    private void siftDown(int[] a, int n, int i) {
        while (true) {
            int left = 2 * i + 1, right = 2 * i + 2, big = i;
            if (left < n && a[left] > a[big]) big = left;
            if (right < n && a[right] > a[big]) big = right;
            if (big == i) return;                // no child is bigger
            int t = a[i]; a[i] = a[big]; a[big] = t;
            i = big;                             // keep sinking
        }
    }
}

How long it takes: bottom up build heap is O(n). Most nodes are near the bottom and can only sink a little. Extra room: a few variables, O(1), since sift down is a loop.

Watch out for

• Start at n / 2 - 1 and move toward 0. Going from the top down does not fix lower levels.
• Swap with the bigger of the two children, not with the first child that happens to be bigger.
• The answer is not unique. Any valid max heap of the same numbers is correct, but the bottom up method gives the one judges usually expect.

What interviewers ask next

• Why is this O(n) and not O(n log n)? Sum the heights of all nodes. Half have height 0, a quarter height 1, an eighth height 2, and the total is less than n.
• Max heap to min heap? Same code with the comparisons flipped.
• Is a sorted array always a heap? A sorted small to big array is a min heap, and big to small is a max heap. The reverse is not true: a heap is usually not sorted.
• Can you do it without knowing it was a min heap? Yes, this method works on any array. That is the point: the old order is thrown away.

Remember this

Grown-up words: the pyramid is a binary heap stored in an array, smallest on top is a min heap, biggest on top is a max heap, sinking is sift down, and fixing from the bottom is build heap (heapify).