Heap sort

A max-heap is a complete binary tree where every parent is at least as large as its children. Stored in an array, the children of index i are 2i + 1 and 2i + 2, and the parent of i is (i - 1) / 2. No pointers are needed.

siftDown(i) fixes a single violation: if a child is larger than the node, swap the node with its larger child and continue from there. It assumes both subtrees are already heaps. The animation shows the array both as a tree and as boxes.

1public static void heapSort(int[] arr) {
2    int n = arr.length;
3    for (int i = n / 2 - 1; i >= 0; i--) {
4        siftDown(arr, n, i);                 // build a max-heap
5    }
6    for (int end = n - 1; end > 0; end--) {
7        swap(arr, 0, end);                   // largest goes to its final slot
8        siftDown(arr, end, 0);               // repair the smaller heap
9    }
10}
11
12static void siftDown(int[] arr, int size, int i) {
13    while (true) {
14        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
15        if (l < size && arr[l] > arr[largest]) largest = l;
16        if (r < size && arr[r] > arr[largest]) largest = r;
17        if (largest == i) return;
18        swap(arr, i, largest);
19        i = largest;
20    }
21}

To build a heap from an arbitrary array, call siftDown on every non-leaf node from the last parent n/2 - 1 down to 0. The leaves are already one-element heaps.

This costs O(n), not O(n log n). A node at height h sifts down at most h levels, and there are about n / 2^(h+1) nodes at height h. The sum of h · n / 2^(h+1) over all h is O(n), because the series Σ h / 2^h converges to 2.

Calling add n times (sift up) also builds a heap, but costs O(n log n).

Phase 2: the maximum is at index 0. Swap it with the last element of the heap, shrink the heap size by one so that element is now outside it and finished, then siftDown(0) to restore the heap property in the smaller heap.

Repeat until the heap has one element. Each extraction costs O(log n), so phase 2 costs O(n log n). The tail of the array fills with the largest values in increasing order, which is why the final array is ascending.

Heap sort needs only a few variables, so it uses O(1) extra memory. Merge sort needs O(n) and quick sort needs O(log n) stack. Together with the worst-case guarantee that is what makes heap sort attractive for memory-constrained systems and for safety-critical code that cannot tolerate quick sort's quadratic worst case.

Quick sort usually beats it in practice. Heap sort jumps between index i and 2i + 1, which is poor for CPU caches, and it does more comparisons: about 2n log₂ n against 1.39 n log₂ n.

Heap sort is not stable. Swapping the root with the last element moves an element across the entire array, and sifting moves it between levels, so equal keys can pass each other.

Example: for [2a, 2b] the build phase does nothing. Extraction swaps the root 2a with 2b, giving [2b, 2a]: order reversed. Run the “Duplicates” preset and compare the a/b tags.