Sort an Array using heap (HeapSort)

The problem, simply

You get an array of numbers. Sort it from small to big. Use a heap to do it, and try to do it inside the same array without a second big array.

A story to remember it

Picture it

The pyramid and the line are the same array. The front part is the heap. The back part is the sorted line, and it grows by one each round.

Examples

Way 1: the simple way

Pour every number into a ready made min heap, Java's PriorityQueue. Then take the smallest out again and again, and write each one into a new array.

1. Add every number to a min heap.
2. Poll the heap n times. Each poll gives the next smallest number.

import java.util.PriorityQueue;

class Solution {
    public int[] heapSortWithExtraSpace(int[] arr) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int x : arr) minHeap.offer(x);       // n inserts
        int[] out = new int[arr.length];
        int i = 0;
        while (!minHeap.isEmpty()) out[i++] = minHeap.poll(); // smallest first
        return out;
    }
}

How long it takes: n inserts and n polls, each O(log n), so O(n log n). Extra room: a second heap and a second array, O(n).

Way 2: the clever way

Use the array itself as a max heap, so no second array is needed.

1. Build a max heap inside the array. Sift down every parent, from index n / 2 - 1 back to 0.
2. For end from n - 1 down to 1:
   • Swap a[0] (the biggest in the heap) with a[end]. That number is now in its final spot.
   • The heap is now one shorter, 0 to end - 1. Sift the new top down inside that smaller heap.
3. When the loop ends, the array is sorted from small to big.

class HeapSort {
    public void sort(int[] a) {
        int n = a.length;
        for (int i = n / 2 - 1; i >= 0; i--) {   // build the max heap
            siftDown(a, n, i);
        }
        for (int end = n - 1; end > 0; end--) {
            int t = a[0]; a[0] = a[end]; a[end] = t; // park the biggest at the back
            siftDown(a, end, 0);                       // heap is now 0..end-1
        }
    }

    // sink a[i] inside the heap a[0..size-1]; a loop, so no call stack
    private void siftDown(int[] a, int size, int i) {
        while (true) {
            int left = 2 * i + 1, right = 2 * i + 2, big = i;
            if (left < size && a[left] > a[big]) big = left;
            if (right < size && a[right] > a[big]) big = right;
            if (big == i) return;
            int t = a[i]; a[i] = a[big]; a[big] = t;
            i = big;
        }
    }
}

How long it takes: building the heap is O(n), then n - 1 rounds each sift down at most log n rows, so O(n log n) in every case, best and worst. Extra room: a few variables, O(1). The sift down is a loop instead of recursion, so there is no hidden call stack.

Watch out for

• For small to big order you need a max heap. A min heap would park the smallest at the back and sort the wrong way.
• Heap sort is not stable. Two equal numbers can swap their order. On [2a, 2b, 1] the result is [1, 2b, 2a].
• The build loop starts at n / 2 - 1, not n - 1. Starting lower is still correct but does useless work on leaves.
• A recursive sift down uses O(log n) stack. The loop version above is truly O(1) extra room.

What interviewers ask next

• Why is building the heap O(n) and not O(n log n)? Most nodes are near the bottom and can only sink a row or two. The sum of all the sink distances is less than 2n.
• Heap sort, quicksort or merge sort? Heap sort has a guaranteed O(n log n) and O(1) room. Quicksort is usually faster in practice because it reads memory in order and is friendly to the cache. Merge sort is stable but needs O(n) room.
• Where is heap sort used for real? Introsort (used by C++ std::sort) starts with quicksort and switches to heap sort when the recursion gets too deep, to avoid the O(n^2) worst case.
• How do you get only the k smallest in order? Build the heap and stop after k rounds, O(n + k log n).
• Can you sort big to small? Use a min heap, or sort small to big and reverse.

Remember this

Grown-up words: the pyramid is a binary max heap, building it from the bottom is heapify (build heap), sliding down is sift down, the back of the line is the sorted suffix, and sorting inside the same array is an in-place sort.