HeapSort: The Underrated Workhorse

HeapSort is probably the least famous of the major sorting algorithms, which is a shame because it has some unique strengths. It guarantees O(n log n) performance like MergeSort, but it's in-place like QuickSort. No worst-case blowups, no extra memory allocation. So why doesn't everyone use it?

The answer: cache performance. HeapSort jumps around memory in ways that make modern CPUs unhappy. But there are scenarios where its guarantees matter more than raw speed, and understanding it teaches you about an incredibly useful data structure: the heap.

What's a Heap Anyway?

Before we can understand HeapSort, we need to understand heaps. A heap is a special kind of binary tree with two properties:

Shape property: It's a complete binary tree (filled left-to-right, level by level)
Heap property: Every parent node is greater than or equal to its children (in a max-heap)

Here's a max-heap:

       16
      /  \
     14   10
    / \   / \
   8   7 9   3
  / \
 2   4

The largest element is always at the root. That's the key insight that makes heaps useful.

Now here's the clever part: we can represent this tree as an array without any pointers:

Array: [16, 14, 10, 8, 7, 9, 3, 2, 4]
Index:   0   1   2  3  4  5  6  7  8

For any element at index i:

Left child is at 2*i + 1
Right child is at 2*i + 2
Parent is at (i-1) // 2

So if you're at index 1 (value 14), your left child is at index 3 (value 8), your right child is at index 4 (value 7), and your parent is at index 0 (value 16). No pointers needed—just arithmetic.

The Big Idea Behind HeapSort

HeapSort works in two phases:

Turn the array into a max-heap (largest element goes to the root)
Repeatedly extract the maximum (swap root with last element, reduce heap size, restore heap property)

After extracting the max, it's already in its final sorted position at the end of the array. Repeat until done.

Let's sort [4, 10, 3, 5, 1]:

Phase 1: Build the heap

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

After heapify: [10, 5, 3, 4, 1]

Tree view:
       10
      /  \
     5    3
    / \
   4   1

Phase 2: Extract maximums

Step 1: Swap 10 with last element (1), reduce heap size
[1, 5, 3, 4 | 10]
        ↑ heap  ↑ sorted

Heapify from root:
[5, 4, 3, 1 | 10]

Step 2: Swap 5 with last heap element (1)
[1, 4, 3 | 5, 10]

Heapify:
[4, 1, 3 | 5, 10]

Step 3: Swap 4 with last heap element (3)
[3, 1 | 4, 5, 10]

Heapify:
[3, 1 | 4, 5, 10]

Step 4: Swap 3 with last heap element (1)
[1 | 3, 4, 5, 10]

Done! Sorted: [1, 3, 4, 5, 10]

The Heapify Operation: Making Things Heap Again

Heapify is the core operation. It takes a node that might violate the heap property and "bubbles it down" to where it belongs.

Here's how it works:

Look at the current node and its two children
Find the largest of the three
If a child is larger than the parent, swap them
Recursively heapify the affected child

Let's say we have this array [1, 14, 10, 8, 7, 9, 3, 2, 4] and we want to heapify starting from the root (index 0, value 1):

       1
      / \
    14   10
   / \   / \
  8   7 9   3
 / \
2   4

Step 1: Compare 1 with children 14 and 10
Largest is 14, so swap 1 and 14:

      14
      / \
     1   10
    / \  / \
   8  7 9   3
  / \
 2   4

Array: [14, 1, 10, 8, 7, 9, 3, 2, 4]

Step 2: Now heapify the affected position (index 1, value 1)
Compare 1 with children 8 and 7
Largest is 8, so swap:

      14
      / \
     8   10
    / \  / \
   1  7 9   3
  / \
 2   4

Array: [14, 8, 10, 1, 7, 9, 3, 2, 4]

Step 3: Heapify index 3 (value 1)
Compare 1 with children 2 and 4
Largest is 4, so swap:

      14
      / \
     8   10
    / \  / \
   4  7 9   3
  / \
 2   1

Array: [14, 8, 10, 4, 7, 9, 3, 2, 1]

Index 7 has no children, so we're done. Heap property restored!

Here's the code:

def heapify(arr, n, i):
    """
    Ensure heap property for subtree rooted at index i
    n is the size of the heap
    """
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    # Check if left child exists and is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # Check if right child exists and is larger than current largest
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # If largest is not root, swap and continue heapifying
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)  # Recursively heapify affected subtree

Building the Initial Heap

To turn an arbitrary array into a heap, you might think you need to heapify every element. Actually, you only need to heapify the non-leaf nodes, and you work backwards from the last non-leaf.

Why? Leaf nodes are already valid heaps by themselves (they have no children to violate the heap property).

The last non-leaf node is at index n//2 - 1 where n is the array length.

def build_max_heap(arr):
    n = len(arr)
    # Start from last non-leaf node and heapify backwards
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

Here's the interesting thing: building a heap from scratch is O(n), not O(n log n) as you might expect. The math is a bit involved, but intuitively, most nodes are near the bottom and need little work, while only a few nodes near the top need to bubble down far.

The Complete HeapSort Algorithm

Putting it all together:

def heapsort(arr):
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        # Move current root (max) to end
        arr[0], arr[i] = arr[i], arr[0]
        
        # Heapify the reduced heap
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# Example
numbers = [4, 10, 3, 5, 1]
heapsort(numbers)
print(numbers)  # [1, 3, 4, 5, 10]

Let me trace through the whole process for [4, 10, 3, 5, 1]:

Build heap phase:

Start: [4, 10, 3, 5, 1]
Last non-leaf: index 1 (value 10)

Heapify index 1: Compare 10 with children (5, none)
10 > 5, no swap needed
[4, 10, 3, 5, 1]

Heapify index 0: Compare 4 with children (10, 3)
10 > 4, swap:
[10, 4, 3, 5, 1]

Heapify index 1: Compare 4 with children (5, 1)
5 > 4, swap:
[10, 5, 3, 4, 1]

Heap built!

Extract phase:

Iteration 1:
Swap root (10) with last (1): [1, 5, 3, 4 | 10]
Heapify index 0 with heap size 4:
  Compare 1 with 5 and 3, swap with 5: [5, 1, 3, 4 | 10]
  Compare 1 with 4, swap: [5, 4, 3, 1 | 10]

Iteration 2:
Swap root (5) with last heap element (1): [1, 4, 3 | 5, 10]
Heapify index 0 with heap size 3:
  Compare 1 with 4 and 3, swap with 4: [4, 1, 3 | 5, 10]

Iteration 3:
Swap root (4) with last (3): [3, 1 | 4, 5, 10]
Heapify: 3 > 1, no change

Iteration 4:
Swap root (3) with last (1): [1 | 3, 4, 5, 10]
Done!

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

Why HeapSort is O(n log n) Always

Building the heap: O(n)

Extracting all elements:

We do n extractions
Each extraction swaps the root and heapifies, which is O(log n)
Total: n × O(log n) = O(n log n)

Overall: O(n) + O(n log n) = O(n log n)

And unlike QuickSort, this is true in all cases. No bad pivot selection can make it slower. The heap structure guarantees it.

The Cache Performance Problem

So why isn't HeapSort more popular if it's always O(n log n) and in-place?

The problem is memory access patterns. When you heapify, you're comparing a parent with children that might be far apart in the array. Modern CPUs load data in "cache lines" (contiguous chunks), and HeapSort constantly accesses non-contiguous memory, causing cache misses.

QuickSort, despite its O(n²) worst case, mostly accesses nearby elements during partitioning. That's cache-friendly. Same with MergeSort's merge step. HeapSort jumping from index 0 to index 3 to index 7? Cache nightmare.

For small arrays where everything fits in cache, this doesn't matter. For large arrays, the cache misses add up.

HeapSort vs The Competition

vs QuickSort:

HeapSort: Guaranteed O(n log n), but slower in practice
QuickSort: Usually faster, but O(n²) worst case
Use HeapSort when worst-case guarantees matter

vs MergeSort:

HeapSort: In-place (O(1) extra space)
MergeSort: Needs O(n) extra space but is stable
Use HeapSort when memory is tight

vs Insertion Sort:

HeapSort: O(n log n) always
Insertion Sort: O(n²) worst case, but O(n) on nearly-sorted data
For tiny arrays (<10 elements), insertion sort is actually faster

When to Actually Use HeapSort

HeapSort shines in specific scenarios:

Embedded systems: Memory is precious, and you can't afford MergeSort's O(n) space or QuickSort's potential O(n²).

Real-time systems: You need guaranteed O(n log n) performance. A medical device or flight control system can't have unpredictable slowdowns.

Security-critical code: QuickSort with bad inputs can be exploited for denial-of-service attacks. HeapSort doesn't have that vulnerability.

Priority queue implementation: If you're already using a heap for a priority queue, you get sorting essentially for free.

The Bigger Picture: Heaps Are Everywhere

Understanding HeapSort teaches you about heaps, which are used constantly in:

Priority queues: Operating system schedulers, network packet routing, event simulation

Dijkstra's algorithm: Finding shortest paths in graphs

Huffman coding: Data compression algorithms

Top-K problems: "Find the 100 largest items in a million-element dataset" is trivial with a heap

Learning HeapSort is less about the sorting algorithm itself (you'll rarely use it directly) and more about understanding heap operations, which show up all over computer science.

Code: Iterative Version

The recursive heapify can cause stack overflow for very large arrays. Here's an iterative version:

def heapify_iterative(arr, n, i):
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < n and arr[left] > arr[largest]:
            largest = left
        
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest == i:
            break  # Heap property satisfied
        
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest  # Continue with the child we swapped with

def heapsort_iterative(arr):
    n = len(arr)
    
    # Build heap
    for i in range(n // 2 - 1, -1, -1):
        heapify_iterative(arr, n, i)
    
    # Extract elements
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify_iterative(arr, i, 0)

Summary: The Trade-offs

HeapSort sits in an interesting middle ground:

Guaranteed performance like MergeSort
Space efficiency like QuickSort
Slower in practice than both

It's not usually the first choice, but when you need its specific combination of guarantees—predictable time, minimal space, no recursion—nothing else quite fits the bill.

The real value in learning HeapSort is understanding heaps themselves. They're a fundamental data structure that solves a whole class of problems. Once you understand heaps, you'll start seeing places to use them everywhere.