What Is Heap Sort?

Heap sort is a comparison-based sorting algorithm that transforms an unsorted array into a binary heap data structure and then repeatedly extracts the largest (or smallest) element to produce a sorted sequence. First proposed by J. W. J. Williams in 1964, heap sort combines the simplicity of selection sort with the efficiency of a priority queue. It operates in-place, meaning it requires only a constant amount of extra space beyond the input array, and guarantees a worst-case time complexity of O(n log n). This reliability makes it a staple in both academic curricula and production systems where predictable performance is essential.

The algorithm relies on the properties of a heap—a complete binary tree where each parent node satisfies the heap property. In a max‑heap, every parent is greater than or equal to its children, so the root holds the maximum element. In a min‑heap, each parent is less than or equal to its children, placing the minimum at the root. Heap sort typically uses a max‑heap to sort in ascending order, but a min‑heap can be used to sort in descending order with minimal changes.

How Heap Sort Works

Heap sort proceeds in two distinct phases: building the heap and then repeatedly extracting the root to build the sorted output. The entire process is performed on the original array without needing additional memory for another array.

Phase 1: Build a Max‑Heap

Given an unsorted array, we first rearrange its elements to satisfy the max‑heap property. Because a heap is a complete binary tree, we can model it using the array indices: the root is at index 0, and for any node at index i, its left child is at 2i + 1 and its right child at 2i + 2. To build a max‑heap we use a "heapify" procedure that starts from the last non‑leaf node (i.e., the parent of the last element) and works upward, sifting each node down to its correct position.

This “bubble‑down” process compares the node with its largest child and swaps them if the child is larger, then repeats recursively on the swapped child until the subtree satisfies the heap property. This single pass, applied from the bottom up, produces a valid max‑heap in O(n) time—a fact that surprises many, but is proven by careful analysis of the heapify operations.

Phase 2: Extraction and Sorting

Once the array is a max‑heap, the largest element sits at the root (index 0). The algorithm swaps this root with the last element of the heap, effectively moving the largest value to its final sorted position at the end of the array. It then reduces the heap size by one (ignoring the now‑sorted element) and calls heapify on the new root to restore the max‑heap property. This cycle—swap, reduce, heapify—repeats until only one element remains in the heap, at which point the entire array is sorted in ascending order.

Detailed Walkthrough with an Example

Consider the unsorted array: [4, 10, 3, 5, 1]. Let's walk through heap sort to see each step.

  1. Build Max‑Heap:
    • Represent the array as a binary tree: root 4, children 10 and 3, grandchildren 5 and 1.
    • Start heapifying from the last non‑leaf node: index 1 (value 10). 10 is already larger than its only child 5, so no change.
    • Move to root index 0 (value 4). Its children are 10 and 3. The largest child is 10; swap 4 and 10. Now the tree has root 10, children 4 and 3, grandchildren 5 and 1.
    • Node at index 1 (now value 4) is not a leaf; it has children 5 and 1. The largest child is 5; swap 4 and 5. The tree becomes: root 10, children 5 and 3, grandchildren 4 and 1. Heap property satisfied.
    Result: [10, 5, 3, 4, 1] — a valid max‑heap.
  2. Extract Maximum:
    • Swap root (10) with last element (1): array becomes [1, 5, 3, 4, 10]. Heap size reduced to 4 (ignore index 4).
    • Heapify root (index 0, value 1): children are 5 and 3. Largest is 5, swap: [5, 1, 3, 4, 10]. Now node index 1 (value 1) has children: 4 (index 3) and no right child. Largest child is 4, swap: [5, 4, 3, 1, 10]. Heap restored.
  3. Second Extraction:
    • Swap root (5) with last element of heap (1): [1, 4, 3, 5, 10]. Heap size 3.
    • Heapify root: children 4 and 3, swap with 4: [4, 1, 3, 5, 10]. Node index 1 (value 1) has child 3 (index 2), no swap needed (1 ≤ 3? Actually 1 < 3, so no swap because we are building max‑heap; we need parent >= children. 1 < 3, so we must swap: [4, 3, 1, 5, 10]. Now heap property holds.
  4. Third Extraction:
    • Swap root (4) with last of heap (1): [1, 3, 4, 5, 10]. Heap size 2.
    • Heapify root: children 3 (index 1), no right child. 1 < 3, so swap: [3, 1, 4, 5, 10].
  5. Fourth Extraction:
    • Swap root (3) with last of heap (1): [1, 3, 4, 5, 10]. Heap size 1, done.

Final sorted array: [1, 3, 4, 5, 10]. This example demonstrates the consistent pattern: build, then repeatedly swap and heapify.

Complexity Analysis

Heap sort offers a well‑understood performance profile:

  • Time Complexity: Building the max‑heap takes O(n) time due to the efficient bottom‑up heapify. Each of the n‑1 extraction steps performs a heapify that costs O(log n), leading to a total of O(n log n) for all extractions. Thus, the overall time complexity is O(n log n) in the worst, average, and best cases. This consistency is a major advantage over quicksort, which can degrade to O(n²).
  • Space Complexity: Heap sort is an in‑place algorithm; it uses only a constant amount of extra storage (typically for a few swap variables). Therefore, its space complexity is O(1).
  • Comparison Swaps: While heap sort guarantees O(n log n) comparisons, it tends to involve more swaps than mergesort or quicksort, especially for large arrays, because of the heapify operations that move elements multiple times across the tree.

When to Use Heap Sort

Heap sort is a strong candidate in specific scenarios, and a poor choice in others. Understanding these trade‑offs helps select the right tool.

Suitable Use Cases

  • Memory‑constrained environments: When you cannot afford the extra O(n) space required by mergesort, heap sort’s in‑place nature is valuable — for example, in embedded systems or when sorting large datasets on devices with limited RAM.
  • Real‑time or safety‑critical systems: Because heap sort never degrades to O(n²), its predictable worst‑case performance makes it suitable for applications where a sorting step must complete within a guaranteed time bound (e.g., in some avionics or medical software).
  • Large datasets with uniform performance requirements: If you need a consistently fast sort with no risk of slow cases, heap sort is reliable.
  • Priority queue implementations: Heap sort is intimately related to heaps; if your system already uses a heap data structure, the sorting step can reuse the same infrastructure.

When to Avoid Heap Sort

  • When stability is required: Heap sort is not stable — it does not preserve the relative order of equal elements. If you need stable sorting (e.g., sorting a table by multiple columns), consider mergesort or insertion sort.
  • For nearly sorted data: On nearly sorted arrays, quicksort with a good pivot strategy or insertion sort can run in near‑linear time, while heap sort still runs in O(n log n).
  • When locality of reference matters: Heap sort accesses memory in a non‑sequential pattern (jumping between child and parent indices), which can cause many cache misses. Quicksort and mergesort often exhibit better cache locality and therefore outperform heap sort in practice on modern hardware.
  • When average‑case speed is paramount: In empirical benchmarks, quicksort is generally 2–3× faster than heap sort on typical data, despite the same asymptotic complexity. The constant factors and cache behavior favor quicksort.

Comparison with Other Sorting Algorithms

To put heap sort in context, consider these common alternatives:

  • Quicksort: Average case O(n log n), worst case O(n²). Quicksort is generally faster in practice but requires careful pivot selection (e.g., median‑of‑three) to avoid worst‑case inputs. It is also not stable, but its in‑place version uses O(log n) stack space.
  • Mergesort: Stable, O(n log n) in all cases, but uses O(n) extra space. It is often preferred for linked lists or when stability is essential.
  • Insertion Sort: O(n²) average, but O(n) on nearly sorted data. In practice, insertion sort beats heap sort for small arrays (typically fewer than 20–50 elements). Many hybrid sorts (like Timsort) use insertion sort for small partitions.
  • Selection Sort: Also in‑place and O(n²), it is simpler but far slower than heap sort on large data.

Heap Sort in Practice

Despite being theoretically elegant, heap sort is less commonly used in standard libraries than quicksort or mergesort. For example, the C++ STL std::sort typically uses introsort (a hybrid of quicksort, heapsort, and insertion sort), which falls back to heap sort when the recursion depth exceeds a limit to guarantee O(n log n). Java’s Arrays.sort for primitives uses dual‑pivot quicksort, while for objects it uses Timsort. Python’s sorted() and list.sort() use Timsort, which does not involve heap sort.

Nevertheless, heap sort’s core idea — the heap data structure — is fundamental. Priority queues, event simulators, graph algorithms (Dijkstra’s shortest path, Prim’s MST), and task schedulers all rely on heaps. Learning heap sort builds intuition for these applications.

You can experiment with heap sort using online visualizations to see the tree transformations: Heap Sort Visualization (University of San Francisco). For more depth, see Wikipedia’s article on Heapsort or the GeeksforGeeks Heap Sort tutorial with implementations in multiple languages.

Advantages and Disadvantages

Advantages

  • Guaranteed O(n log n) worst‑case: Unlike quicksort, heap sort never falls into an O(n²) trap, making it robust for adversarial or unknown inputs.
  • In‑place sorting: Uses only O(1) extra memory, suitable for environments with strict memory limits.
  • No recursion overhead: The iterative heapify operations avoid function call overhead, which can benefit systems where recursion depth is limited.
  • Simple to implement from scratch: The algorithm’s logic is straightforward once you understand the heap property and the heapify procedure.

Disadvantages

  • Unstable: Equal elements may have their original order changed. If stability matters, heap sort is not the choice.
  • Poor cache performance: The jumpy memory access pattern of heapify (accessing indices 2i+1 and 2i+2) leads to cache misses, especially on large datasets.
  • Slower than quicksort in practice: Empirical studies consistently show that quicksort’s better cache locality and lower constant factors make it 2–3× faster on typical random data.
  • Not adaptive: Heap sort does not exploit existing order in the input. It always performs a full build and n‑1 extractions, regardless of how sorted the data already is.

Conclusion

Heap sort remains a fundamental algorithm in computer science. Its guaranteed O(n log n) runtime and in‑place operation make it an excellent candidate when worst‑case predictability and memory economy are more important than raw speed or stability. While it rarely dominates in standard library sorting — where Timsort, introsort, or quicksort are preferred — the heap data structure behind it is indispensable. Mastering heap sort gives developers a deeper understanding of algorithmic design trade‑offs and practical tools for building efficient priority queues, schedulers, and graph algorithms.

When choosing a sorting algorithm for your next project, weigh the factors: is memory scarce? Is worst‑case time critical? Do you require stability? For many applications, heap sort’s blend of simplicity, efficiency, and consistency makes it a worthy option — especially as a fallback when other methods could falter. Understanding when to reach for heap sort — and when to leave it on the shelf — is the mark of an experienced engineer.