Java Heap Sort Using Binary Heap In Place

Introduction

The heap sort java tutorial is the third of the standard O(n log n) comparison sorts and the only one that is both in place and guaranteed O(n log n) in the worst case. J. W. J. Williams invented heap sort in 1964 in his paper Algorithm 232: Heapsort, published in Communications of the ACM. Robert Floyd followed in the same year with Algorithm 245: Treesort 3, which gave the linear time heap construction algorithm that is now standard. Together, Williams and Floyd produced the heap sort we teach today: build a max heap in O(n), then repeatedly extract the maximum into the back of the array.

For a Java learner, the heap sort java tutorial explains why the algorithm is the right choice when worst case performance matters and extra memory is unavailable, why java.util.PriorityQueue is built on the same binary heap representation, and why heap sort is not stable. Building heap sort in place is the cleanest way to internalise the binary heap array representation that underlies priority queues throughout the JDK.

What is Heap Sort?

Heap sort is a comparison based sorting algorithm that operates in two phases. The first phase builds a max heap from the input array in place. A max heap is a binary tree stored in an array such that every parent is greater than or equal to its children. The second phase repeatedly swaps the root (the maximum element) with the last element of the heap, decrements the heap size, and sifts the new root down to restore the heap property. After n - 1 such extractions, the array is sorted in ascending order.

Heap sort belongs to the O(n log n) comparison sort category, alongside merge sort and quicksort. It is in place (O(1) extra memory). It is not stable, because the sift-down operation can move equal elements past each other. The worst case, average case, and best case are all O(n log n), because the algorithm performs the same work regardless of input order. The constant factors are larger than quicksort's on average, which is why the JDK prefers quicksort for primitives.

The array representation of a binary heap maps the tree into index positions. For a node at index i, the parent is at (i - 1) / 2, the left child is at 2 * i + 1, and the right child is at 2 * i + 2. This representation wastes no memory on pointers and gives O(1) parent and child calculations, which is why java.util.PriorityQueue uses it.

How Heap Sort Works - Step by Step

Step 1: Build max heap. Start from the last non leaf node, which is at index (n / 2) - 1. Walk backwards to index 0, calling siftDown on each node. SiftDown swaps a node with its larger child until the node is greater than or equal to both children (or until it is a leaf). The build phase runs in O(n) because most nodes are near the leaves and require little sifting.

Step 2: Extract maximum. Swap arr[0] (the root, which is the maximum) with arr[n - 1] (the last heap element). Now the maximum is at its final sorted position at the back of the array. Decrement the heap size by 1.

Step 3: Sift down the new root. The new root (formerly the last heap element) is probably small, so call siftDown on index 0 with the new heap size. The sift restores the max heap property on the remaining heap.

Step 4: Repeat. Repeat steps 2 and 3 for heap sizes n - 1, n - 2, ..., 1. After n - 1 iterations, the array is sorted in ascending order, because the maximums have been placed at the back one by one.

Step 5: Concrete example on [5, 3, 8, 4, 2]. Build max heap: start at index (5 / 2) - 1 = 1 (value 3). SiftDown index 1: children are 2*1+1 = 3 (value 4) and 2*1+2 = 4 (value 2). Larger child is 4 at index 3. 3 < 4, so swap: array becomes [5, 4, 8, 3, 2]. Continue siftDown from index 3: children would be 7 and 8, both out of heap range, so stop. Now siftDown index 0 (value 5): children are index 1 (value 4) and index 2 (value 8). Larger child is 8 at index 2. 5 < 8, so swap: array becomes [8, 4, 5, 3, 2]. Continue siftDown from index 2: children are 5 and 6, out of heap range, so stop. Max heap is [8, 4, 5, 3, 2].

Step 6: Extract maximum. Swap arr[0] = 8 with arr[4] = 2: array becomes [2, 4, 5, 3, 8]. Heap size is now 4. SiftDown index 0 (value 2): children are index 1 (value 4) and index 2 (value 5). Larger is 5 at index 2. 2 < 5, swap: array becomes [5, 4, 2, 3, 8]. Continue siftDown from index 2: children are 5 and 6, both out of range (heap size 4 means indices 0-3 are valid), so stop. Swap arr[0] = 5 with arr[3] = 3: array becomes [3, 4, 2, 5, 8]. Heap size is 3. SiftDown index 0 (value 3): children are index 1 (value 4) and index 2 (value 2). Larger is 4. 3 < 4, swap: array becomes [4, 3, 2, 5, 8]. Children of index 1 are 3 and 4, out of range, so stop. Swap arr[0] = 4 with arr[2] = 2: array becomes [2, 3, 4, 5, 8]. Heap size is 2. SiftDown index 0 (value 2): children are index 1 (value 3). 2 < 3, swap: array becomes [3, 2, 4, 5, 8]. Children of index 1 are 3 and 4, out of range, stop. Swap arr[0] = 3 with arr[1] = 2: array becomes [2, 3, 4, 5, 8]. Heap size is 1. SiftDown index 0: no children, stop. Array is sorted.

Step 7: Complexity. Build heap is O(n) using the Floyd linear construction. Each of the n - 1 extractions performs one O(log n) sift-down, giving O(n log n) total. The overall complexity is O(n log n) worst case, average case, and best case. Space is O(1) extra.

Java Program for Heap Sort

public class HeapSortDemo {

    static void heapSort(int[] arr) {
        int n = arr.length;
        // Build max heap: start from last non-leaf, sift down to root.
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
        // Extract maximum one at a time into the back.
        for (int heapSize = n - 1; heapSize > 0; heapSize--) {
            swap(arr, 0, heapSize);
            siftDown(arr, heapSize, 0);
        }
    }

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

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    static void printArray(int[] arr) {
        for (int x : arr) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        System.out.print("before: ");
        printArray(arr);
        heapSort(arr);
        System.out.print("after:  ");
        printArray(arr);

        int[] arr2 = {12, 11, 13, 5, 6, 7};
        System.out.print("before: ");
        printArray(arr2);
        heapSort(arr2);
        System.out.print("after:  ");
        printArray(arr2);
    }
}

Code Explanation - Line by Line

The heapSort method first builds a max heap, then extracts maximums one by one. The build loop starts at i = n / 2 - 1, which is the index of the last non leaf node (the parent of the last element). Walking backwards to 0 ensures that children are sifted before their parents, which is the key to the linear build time. Each siftDown call moves the element at i down to its correct position in the partial heap below it.

The extraction loop starts with heapSize = n - 1 and decrements to 1. Each iteration swaps the root (the maximum) with the last element of the current heap, then calls siftDown on index 0 with the decremented heapSize. The effect is that the maximum moves to its final sorted position at the back of the array, and the remaining heap is restored.

The siftDown method is the workhorse. It computes the left and right child indices (2 * i + 1 and 2 * i + 2). The bounds check left < heapSize and right < heapSize ensures we do not read past the heap boundary, which is essential after extractions have shrunk the heap. The largest variable tracks which of the parent and its two children is the maximum. If the parent is already the largest, the method returns. Otherwise, the parent is swapped with the largest child, and i is updated to that child's index to continue sifting down.

The swap and printArray helpers are the same as in bubble sort and selection sort. The main method runs the sort on [5, 3, 8, 4, 2] and on [12, 11, 13, 5, 6, 7] to show correctness on different inputs.

Sample Input and Output

Input:  arr = {5, 3, 8, 4, 2}
        heapSort(arr)
        arr = {12, 11, 13, 5, 6, 7}
        heapSort(arr)
Output:
        before: 5 3 8 4 2
        after:  1 2 3 4 5
        before: 12 11 13 5 6 7
        after:  5 6 7 11 12 13

Both inputs are sorted in ascending order. The first run produces [2, 3, 4, 5, 8] from [5, 3, 8, 4, 2]. The second run produces [5, 6, 7, 11, 12, 13] from [12, 11, 13, 5, 6, 7]. The output verifies that the build heap and extract phases work together to produce a sorted array without any extra memory allocation.

Common Mistakes to Avoid

First, using arr[left] >= arr[largest] instead of arr[left] > arr[largest]. The >= comparison would update largest on equal values, causing extra swaps and breaking the in place heap property on arrays with duplicates. Second, forgetting the bounds check left < heapSize. Without it, the sift reads past the heap boundary into the sorted region at the back of the array, which corrupts the sort. Third, building the heap with sift-up instead of sift-down. Sift-up build is O(n log n); the linear Floyd construction uses sift-down starting from the last non leaf. Fourth, recursing on the heap boundary instead of decrementing it. The extraction loop must shrink the heap by one each iteration; otherwise, the same maximum is re-extracted forever.

Real-World Applications

Heap sort is the algorithm of choice when worst case performance and memory constraints both matter. Embedded systems with hard real time deadlines and limited RAM use heap sort because it cannot degrade below O(n log n) and uses no extra memory. The Linux kernel uses heap sort in some places where stability is not required and worst case bounds matter.

The binary heap that underlies heap sort is also the data structure behind java.util.PriorityQueue, which is used in Dijkstra's shortest path, Prim's minimum spanning tree, the A star search, Huffman coding, event driven simulation, and operating system process schedulers. Understanding heap sort therefore directly teaches you the data structure that powers priority queue based algorithms throughout the JDK. Production schedulers in Hadoop YARN, Kubernetes, and Linux's Completely Fair Scheduler all use priority queue abstractions that, at their core, are binary heaps.

Conclusion

We built heap sort with the linear build heap and the iterative sift-down, walked through a five element example, and saw why the algorithm is O(n log n) in every case with O(1) extra memory. The binary heap array representation is the same one used by java.util.PriorityQueue, so the algorithm is directly applicable to production code. Next, study counting sort and radix sort for non comparison sorts that achieve O(n) on integer keys, then move on to the priority queue abstraction built on the same heap representation.