Heap Sort Explained: How It Works, Why It's Fast, and When to Use It

Every developer eventually hits a moment where a simple sort isn't good enough — maybe memory is tight, or a worst-case O(n²) from quicksort would be catastrophic in production. Heap sort was designed precisely for those moments. It's used inside priority queues, operating system schedulers, and graph algorithms like Dijkstra's — anywhere you need a guaranteed, predictable sort that never blows up under adversarial input.

The core problem heap sort solves is the tension between speed and memory. Merge sort is also O(n log n), but it needs O(n) extra space to do its work. Quicksort is fast on average but degrades to O(n²) on already-sorted or reverse-sorted data. Heap sort gives you O(n log n) in every case — best, average, and worst — while sorting the array in-place using only O(1) extra space. That's a rare combination.

By the end of this article you'll understand what a max-heap actually is and why it matters, how heapify is the secret engine behind the whole algorithm, how to implement heap sort from scratch in Java with a clear mental model you won't forget, and exactly when to reach for it over quicksort or merge sort in real projects.

How Heap Sort Works — Plain English and Algorithm

Heap sort has two phases: build a max-heap from the array, then repeatedly extract the maximum to produce a sorted array.

A max-heap is a complete binary tree where every parent is larger than its children. The maximum element is always at the root (index 0). We can represent the heap in the same array without extra space: for a node at index i, its left child is at 2i+1 and right child at 2i+2.

Phase 1 — Build a max-heap in O(n): 1. Start from the last non-leaf node (index n//2 - 1) and work backward to index 0. 2. For each node, run 'heapify down': if either child is larger, swap with the larger child and recurse. 3. After processing all nodes, the array satisfies the max-heap property.

Phase 2 — Sort by extracting elements in O(n log n): 4. Swap the root (maximum) with the last element. The maximum is now in its final sorted position. 5. Reduce the heap size by 1 (ignore the last element which is now sorted). 6. Run heapify down on the new root to restore the max-heap property. 7. Repeat steps 4-6 until the heap has one element.

Time complexity: O(n log n) for all cases. Space: O(1) — heap sort is in-place.

Worked Example — Tracing Heap Sort on [4, 10, 3, 5, 1]

Input: [4, 10, 3, 5, 1]

Phase 1 — Build max-heap. Last non-leaf = index 1 (node value 10). Heapify index 1 (value 10): children are index 3 (5) and 4 (1). 10 > both. No swap. Heapify index 0 (value 4): children are index 1 (10) and 2 (3). 10 > 4. Swap 4 and 10. Array: [10, 4, 3, 5, 1]. Now heapify the displaced 4 at index 1: children 5 and 1. 5>4. Swap. Array: [10, 5, 3, 4, 1]. Max-heap built.

Phase 2 — Sort: Iteration 1: Swap root 10 with last element 1. Array: [1, 5, 3, 4, |10]. Heap size=4. Heapify root 1: children 5, 3. 5>1. Swap. Array: [5, 1, 3, 4, |10]. Heapify 1 at index 1: children 4. 4>1. Swap. Array: [5, 4, 3, 1, |10]. Iteration 2: Swap root 5 with 1. Array: [1, 4, 3, |5, 10]. Heap size=3. Heapify root 1: children 4, 3. 4>1. Swap. Array: [4, 1, 3, |5, 10]. Heapify 1 at index 1: no children in heap. Done. Iteration 3: Swap root 4 with 3. Array: [3, 1, |4, 5, 10]. Heap size=2. Heapify root 3: child 1. 3>1. No swap. Iteration 4: Swap root 3 with 1. Array: [1, |3, 4, 5, 10]. Heap size=1. Done.

Final sorted array: [1, 3, 4, 5, 10]

Heap Sort Implementation

Heap sort is implemented in two phases. The build-heap phase constructs a max-heap in-place by calling sift-down (heapify) on every non-leaf node from right to left, taking O(n) total time (not O(n log n) — most nodes are near the bottom and require little sifting). The extraction phase repeatedly swaps the root (maximum element) with the last element of the current heap, reduces the heap size by 1, and sifts the new root down to restore the heap property. Each sift-down is O(log n), and we do n-1 extractions, giving O(n log n) total. Heap sort is not stable and has poor cache performance because of non-sequential memory access during sifting, making quicksort faster in practice despite the same asymptotic complexity.

def heap_sort(arr):
    n = len(arr)

    # Phase 1: Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Phase 2: Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # move current max to end
        heapify(arr, i, 0)  # restore heap property

def heapify(arr, heap_size, root):
    largest = root
    left    = 2 * root + 1
    right   = 2 * root + 2

    if left < heap_size and arr[left] > arr[largest]:
        largest = left
    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, heap_size, largest)

arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)

Frequently Asked Questions