Heapsort explained: how it works, code and complexity

The idea in plain words

Heapsort is selection sort with a faster way to find the maximum. Selection sort scans the whole unsorted part, O(n) each time. Heapsort keeps the unsorted part as a heap, so the maximum is always at index 0 and restoring order after removing it costs only O(log n).

A binary heap is stored in a plain array without pointers. For the element at index i:

• the left child is at 2*i + 1 and the right child at 2*i + 2;
• the parent is at (i - 1) // 2;
• in a max-heap, every parent is greater than or equal to its children, so the largest element is at index 0.

1. Build a max-heap from the array by sifting down every non-leaf node, starting from the last one and moving to index 0.
2. Swap the root (the maximum) with the last element of the heap. That element is now in its final place.
3. Shrink the heap by one and sift the new root down until the heap property holds again.
4. Repeat steps 2 and 3 until the heap has one element.

Worked example, step by step

Sort [4, 10, 3, 5, 1]. Elements after the bar are sorted and final.

Python implementation

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

Python's heapq module provides a min-heap on a plain list. Popping every element gives a sorted list, which is a short (not in-place) heapsort:

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

Time and space complexity

Building the heap bottom-up is O(n), not O(n log n), because the sum of node heights in a complete binary tree is O(n). The extraction phase dominates the total.

How heapsort compares with other sorts

Heapsort is not stable: swapping the root to the end can carry an element past others with the same key. Its main strengths are a guaranteed O(n log n) worst case together with O(1) extra space, a combination neither quicksort nor merge sort offers. Its weakness is memory access: jumping between index i and 2*i + 1 uses CPU caches poorly, so it is typically slower than a well-implemented quicksort. Introsort uses heapsort as a fallback when quicksort recurses too deeply.

Variants and common mistakes

• Partial sorting: to get only the k largest items, build the heap and extract k times, O(n + k log n). In Python, heapq.nlargest and heapq.nsmallest do this.
• Top-k from a stream: keep a min-heap of size k and push or replace each new item, O(n log k) time and O(k) memory.
• Bottom-up heapsort sifts the hole down to a leaf first and then up, which saves comparisons.
• Smoothsort, a heap-based variant by Dijkstra, runs in O(n) on already sorted input but is rarely used because it is complex.

When to use heapsort

Use heapsort when you need a guaranteed O(n log n) worst case with no extra memory, for example in embedded or real-time systems, or as a safety fallback inside another sort. For everyday Python code, use sorted(), which is stable and faster on typical data. The heap itself is more useful than the sort: priority queues, Dijkstra's shortest paths, schedulers, merging k sorted lists (heapq.merge) and finding the k largest values all build on it. Interviews often ask for the heap index formulas, why heap building is O(n), and the top-k problem.