Heapsort

Heapsort is a comparison sort that uses a binary heap to repeatedly extract the maximum. It runs in O(n log n) time, in place, with O(1) extra space — the only mainstream comparison sort with all three properties.

Complexity

How it works

First, heapify the array into a max-heap in O(n). Then repeatedly: swap the root (largest element) with the last element of the heap, shrink the heap by one, and sift the new root down. After n iterations the array is sorted ascending.

Python implementation

def heapsort(arr):
    """In-place heapsort using a max-heap."""
    n = len(arr)

    def sift_down(start, end):
        root = start
        while 2 * root + 1 < end:
            child = 2 * root + 1
            if child + 1 < end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                return

    for start in range(n // 2 - 1, -1, -1):
        sift_down(start, n)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end)
    return arr


print(heapsort([3, 6, 1, 8, 2, 9, 4]))  # [1, 2, 3, 4, 6, 8, 9]

Trade-offs

• In-place, O(1) auxiliary memory.
• Guaranteed O(n log n) — no quicksort-style worst case.
• Not stable.
• Slower than quicksort in practice due to poor cache locality (jumps around the heap).

← Back to Algorithms

1. Summary

Heapsort sorts in two phases. Phase one turns the array into a max-heap, a complete binary tree stored in the array itself in which every parent is at least as large as its children. Phase two repeatedly swaps the root, which is the maximum of the remaining heap, into the last unsorted slot and restores the heap property on the shrunken prefix. Because every operation happens inside the original array, the extra memory is constant. Because the heap has height log n, each extraction costs O(log n), and the total is O(n log n) in every case, with no worst-case input that degrades it the way a bad pivot degrades quicksort.

2. Step-by-step trace

The first row is the input. Bottom-up heapify starts at the last internal node (index n//2 - 1) and sifts each node down, which yields the max-heap in the second row. Each following row shows one extraction: the root is swapped with the last element of the heap, the boundary moves one place left, and the new root is sifted down until both children are smaller. The green suffix grows by one element per step and is already in final position. After n - 1 extractions the whole array is sorted.

3. The implicit heap layout

A heap needs no node objects. Position arithmetic replaces pointers: the children of index i are 2i + 1 and 2i + 2. This compactness is what makes heapsort in-place. It is also the source of its main practical weakness: sifting down jumps between distant indices on large arrays, so memory access is far less cache-friendly than the sequential scans of mergesort or the partition loop of quicksort.

Bottom-up heapify is O(n), not O(n log n), because most nodes are near the bottom and sift only a short distance; the sum of heights over all nodes is bounded by n.

4. Worked example and variants

The standard library exposes heaps through heapq, which implements a min-heap. Popping n times gives a sorted list but uses O(n) extra space; the in-place version above is the real heapsort. heapq is more commonly used for partial sorting, such as the k smallest elements.

import heapq, random

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

data = [random.randint(0, 99) for _ in range(12)]
assert heapsort_heapq(data) == sorted(data)

# Partial sort: top-3 largest without sorting everything, O(n log k)
print(heapq.nlargest(3, data))
print(heapq.nsmallest(3, data))

Two well-known variants are worth knowing. Introsort, used by many C++ standard libraries for std::sort, starts with quicksort and switches to heapsort when recursion gets too deep, which caps the worst case at O(n log n). Bottom-up heapsort reduces comparisons by sifting the hole to a leaf first and then bubbling the element up.

5. Trade-offs and when to use

Choose heapsort when memory is fixed and a guaranteed worst case matters, for example in embedded or real-time code, or as the fallback inside introsort. In everyday Python, use sorted(), which is Timsort; use heapq for priority queues and top-k problems.

6. Pitfalls

• Forgetting to shrink the heap boundary after each swap, which re-sifts already sorted elements.
• Starting heapify from index 0 and moving forward; it must go from n//2 - 1 down to 0.
• Expecting stability: equal keys can be reordered.
• Off-by-one errors on the right child check (child + 1 < end).

7. Related topics

• Quicksort
• Mergesort
• Timsort
• Efficient sorts overview

Featured Videos