☕ Buy me a coffee — $3

Heap Sort

Overview

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It builds a max heap (for ascending order) from the input array and repeatedly extracts the maximum element from the heap, placing it at the end of the sorted portion of the array.

Heap Sort provides guaranteed O(n log n) time complexity in all cases while using only O(1) extra space, making it an excellent choice when you need in-place sorting with predictable performance.

Its position in the sorting landscape is unique: it is the only well-known algorithm that is simultaneously in-place (O(1) auxiliary space) and worst-case optimal (O(n log n)). Quicksort is in-place but has O(n²) worst case. Mergesort has O(n log n) worst case but needs O(n) auxiliary space on arrays. Heap sort achieves both bounds at once, and that is why it survives despite being slower than quicksort in the average case, when either condition is a hard requirement, no other algorithm delivers.

History

Heap sort was invented by J.W.J. Williams in 1964 and appeared in Communications of the ACM as "Algorithm 232: Heapsort." What Williams contributed was not the general idea of selection sort with a fast "find the maximum" step, that idea is older, but the specific data structure now called the binary heap and the observation that it could be embedded in an array without any explicit pointers, using the parent-at-i, children-at-2i+1-and-2i+2 arithmetic. That embedding is what makes heap sort in-place: the heap and the sorted output share the same array, growing from opposite ends.

Robert W. Floyd made a crucial refinement in 1964, published as "Algorithm 245: Treesort 3." Floyd showed that building a heap from an unsorted array can be done in O(n) time by working bottom-up, not the O(n log n) that the naive "insert n elements one at a time" analysis suggests. The proof is a beautiful piece of amortised analysis: most nodes are near the bottom of the tree, where sift-down travels only a short distance, so summing the total sift-down work across all levels of a complete binary tree telescopes to O(n) rather than O(n log n). This is one of the most widely misquoted results in algorithms; you will often see "building a heap is O(n log n)" in textbooks, which is a valid but loose upper bound rather than the true asymptotic behaviour.

The binary heap itself has become one of the most important data structures in computing outside of heap sort's context. It is the standard implementation of the priority queue, which appears in Dijkstra's shortest-path algorithm, in A* search, in event-driven simulation, in job schedulers, and in nearly every operating system kernel. Python exposes it directly through heapq; C++ has std::priority_queue; Java has PriorityQueue. When you use those classes you are using Williams's data structure whether or not you ever call it a heap.

How It Works

The algorithm follows these steps:

  1. Build Max Heap: Convert the array into a max heap structure
  2. Extract Maximum: Swap the root (maximum element) with the last element
  3. Heapify: Restore the heap property for the reduced heap
  4. Repeat: Continue until the heap is empty

A max heap is a complete binary tree where each parent node is greater than or equal to its children. This property ensures the maximum element is always at the root.

Algorithm


HeapSort(arr):
    n = length of arr
    
    # Build max heap
    for i = n/2 - 1 down to 0:
        Heapify(arr, n, i)
    
    # Extract elements from heap one by one
    for i = n - 1 down to 1:
        swap arr[0] and arr[i]  # Move root to end
        Heapify(arr, i, 0)      # Heapify reduced heap

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:
        swap arr[i] and arr[largest]
        Heapify(arr, n, largest)

Implementation


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

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)

Complexity Analysis

  • Time Complexity: O(n log n) in all cases (best, average, and worst)
    • Building the heap: O(n)
    • Extracting n elements: O(n log n)
    • Total: O(n log n)
  • Space Complexity: O(log n) as written below, because heapify recurses to a depth equal to the tree height. Rewriting the sift-down as an iterative loop (shown below) makes it genuinely O(1), which is heap sort's main selling point.
def heapify_iterative(arr, n, i):
    """Sift-down without recursion - true O(1) auxiliary space."""
    while True:
        largest = i
        left, right = 2 * i + 1, 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:
            return
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

Unlike Quick Sort, Heap Sort guarantees O(n log n) regardless of input, which makes it predictable. Note that building the heap is O(n), not O(n log n), a frequently misquoted result. Most nodes sit near the bottom of the tree and sift down only a short distance; summing height×count over all levels telescopes to O(n).

So why is heap sort not the default sort anywhere? Cache behaviour. Sift-down jumps between indices i, 2i+1, 4i+3 and so on, which scatters accesses across memory and misses cache constantly. Quicksort scans linearly and, despite its O(n²) worst case, typically runs two to three times faster on real hardware. Heap sort's practical role today is as the safety net inside introsort: quicksort runs, and if recursion gets too deep, the implementation switches to heap sort to guarantee the O(n log n) bound.

Characteristics

  • Stable: No - does not preserve relative order of equal elements
  • In-place: Yes - only requires O(1) extra space
  • Adaptive: No - always performs the same operations
  • Online: No - requires the entire array to be present

Why Heap Sort Is Slower Than Quicksort in Practice

The complexity table says heap sort and quicksort both average O(n log n), which suggests they should perform similarly. On real hardware they do not: quicksort is typically two to three times faster than heap sort at large n, and the reason is entirely about cache behaviour.

Modern CPUs are much faster than main memory. To hide the memory-access latency, they read data in cache lines of 64 bytes at a time, and they pre-fetch subsequent cache lines speculatively based on the pattern of your accesses. Quicksort's partition step walks the array sequentially from both ends toward the middle, the pattern the hardware is specifically designed to accelerate. It stays in L1 and L2 cache almost perfectly.

Heap sort's sift-down does the opposite. Starting at index i, it jumps to 2i+1, then 4i+3, and so on. For an array that does not fit in L1 cache, each of those jumps is likely to be a cache miss, and the hardware prefetcher cannot help because the access pattern is not linear. A single sift-down through a heap of a million elements can involve ~20 cache misses, each costing on the order of 100 CPU cycles. Over n sift-downs, that is 2 billion wasted cycles, enough to make heap sort visibly slower than quicksort on the same machine.

The consequence in production code: heap sort is almost never used as the primary sort algorithm in a standard library, despite its guarantees. Instead it appears as the safety fallback inside introsort, the algorithm C++'s std::sort and (until recently) Rust's sort_unstable use. Introsort runs quicksort by default, monitors the recursion depth, and switches to heap sort if the depth exceeds a threshold like 2 log2 n. This gives you quicksort's speed on typical input and heap sort's O(n log n) worst-case guarantee against adversarial input, with the cache-unfriendly heap sort executing only when quicksort has already demonstrated it is misbehaving.

Related Algorithms and Variants

Priority Queue Operations

The heap data structure is more important than heap sort itself. Beyond sorting, it supports:

  • insert(x) in O(log n), append at the end and sift up
  • extract-min in O(log n), take the root, replace with the last element, and sift down
  • peek in O(1), the root is always the extremum
  • build-heap in O(n). Floyd's bottom-up construction
  • decrease-key in O(log n), when the position of the key is known

These operations are what Dijkstra's shortest-path algorithm and Prim's minimum spanning tree both rely on. Every graph algorithm chapter that mentions a "priority queue" is describing a binary heap under the hood.

d-ary Heaps

Generalising the binary heap to a heap where each node has d children rather than 2 gives a d-ary heap. Increasing d makes insertions cheaper (sift-up traverses a shallower tree, height = logd n) at the cost of more expensive extractions (sift-down must scan d children per level). For Dijkstra's algorithm, choosing d = m/n (where m is edges and n is vertices) minimises total work, a nice example of the theory affecting the choice of data structure.

Fibonacci Heaps

Fibonacci heaps, introduced by Fredman and Tarjan in 1984, give amortised O(1) insert and decrease-key with O(log n) extract-min. They yield the theoretically best complexity for Dijkstra's algorithm at O(E + V log V). The constants are so large that in practice a plain binary heap beats a Fibonacci heap on almost all inputs; the algorithm is important theoretically but rarely used in production code.

Pairing Heaps and Rank-Pairing Heaps

A simpler alternative to Fibonacci heaps with similar amortised bounds and much smaller constants. Pairing heaps are competitive with binary heaps on most workloads and beat them when decrease-key is frequent.

Smoothsort

Edsger Dijkstra's 1981 sorting algorithm, designed to be O(n log n) worst case but adaptive, running in O(n) on already-sorted input, unlike plain heap sort. It uses a Leonardo heap (a forest of heaps sized by Leonardo numbers) instead of a binary heap. Smoothsort is theoretically elegant but the implementation is complex and it is rarely used; Timsort achieves similar adaptivity through simpler means.

Common Misconceptions

  • "Building a heap is O(n log n)." A widely-repeated result that is true but loose. The tight bound is O(n), by Floyd's telescoping argument described above. If you see this in a textbook, it is not wrong, O(n log n) is a valid upper bound, but O(n) is achievable and standard.
  • "Heap sort is stable." No. When we swap the root of the heap with the last element, we can move an equal element past a copy of itself, breaking the input-order guarantee. There is no easy way to make heap sort stable without O(n) extra space to track original positions. If you need stability, use merge sort or Timsort.
  • "You should use a min heap for ascending sort." Counter-intuitively, no. To sort ascending using a heap that sorts in-place, you use a max heap: extract the max, put it at the end, shrink the heap, repeat. Using a min heap would require O(n) extra space to hold the extracted elements in order.
  • "Heap sort is always O(n log n)." True in the worst case, but subtle input structure does not speed it up either, heap sort is not adaptive. Even a sorted input takes Θ(n log n) because every extraction still requires a sift-down of depth log n. Contrast with insertion sort or Timsort, which handle sorted input in O(n).

When to Use Heap Sort

Heap sort has a narrower place in modern practice than its theoretical properties suggest, but that place is genuine and important. Use it when:

  • You need worst-case O(n log n) with O(1) space. This combination is unique to heap sort and is what makes it valuable in environments where you cannot risk either quicksort's O(n²) worst case or mergesort's O(n) memory. Real-time systems, safety-critical firmware, and adversarial network services all use heap sort for this reason.
  • Inside introsort as a fallback. This is by far its most common use in modern code. Introsort runs quicksort normally and switches to heap sort if the recursion depth crosses 2 log n, ensuring adversarial input cannot trigger the O(n²) worst case.
  • When you are already using a heap for something else. If your data is already in a heap-shaped structure, a priority queue, an event list, extracting all elements in order costs O(n log n) using heap sort's mechanics, no new code needed.
  • For selecting the top-k elements. A max-heap of size k, streaming through n input elements, gives you the k largest in O(n log k). This is a common pattern for "find the top 10 largest values from this data stream" problems and is essentially a bounded heap sort.

Prefer quicksort or introsort as your general-purpose unstable sort. Prefer merge sort or Timsort when you need stability. Reach for heap sort when guarantees matter more than average speed.

Understanding the Heap Structure

In a max heap represented as an array:

  • Parent at index i has children at indices 2i+1 and 2i+2
  • Child at index i has parent at index (i-1)/2
  • The root (maximum element) is at index 0
  • The heap property: arr[parent] >= arr[child] for all nodes

Example

Sorting [12, 11, 13, 5, 6, 7]: 

Build max heap:
        12
      /    \
    11      13
   /  \    /
  5    6  7

After heapify:
        13
      /    \
    11      12
   /  \    /
  5    6  7

Extract and sort:
Step 1: Swap 13 and 7, heapify
Step 2: Swap 12 and 6, heapify
Step 3: Swap 11 and 5, heapify
...
Final: [5, 6, 7, 11, 12, 13]

Related Algorithms

Explore other sorting algorithms: