Heapsort is a comparison-based in-place sorting algorithm that first builds a max-heap from the input array, then repeatedly extracts the maximum element to produce a sorted sequence — achieving Θ(n log n) time in all cases with O(1) auxiliary space.
Heapsort turns the array into a max-heap — a shape where every parent is larger than its children — then repeatedly extracts the maximum, building the sorted result in-place.
What a heap is
A max-heap is a binary tree where every node is larger than or equal to both its children. The maximum element is always at the root. A heap can be stored in an array: for a node at index i, its left child is at 2i+1, its right child at 2i+2, and its parent at ⌊(i-1)/2⌋. No pointers needed — the tree structure is implicit in the array positions.
def heapsort(arr):
n = len(arr)
# Phase 1: build max-heap from the array (bottom-up)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Phase 2: extract elements one by one
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # move max to end
heapify(arr, i, 0) # restore heap on reduced array
def heapify(arr, n, i):
"""Sift down node i in a heap of size n."""
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:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest) # sift the displaced node down
arr = [5, 2, 8, 1, 9, 3, 7]
heapsort(arr)
print(arr) # [1, 2, 3, 5, 7, 8, 9]Complexity
| Case | Time | Space | Notes |
|---|---|---|---|
| Best | Θ(n log n) | O(1) | |
| Average | Θ(n log n) | O(1) | |
| Worst | Θ(n log n) | O(1) | Always O(1) extra space — truly in-place |
Two phases
Phase 1 — Build heap: starting from the last non-leaf node (index n/2−1) and working backwards, call heapify on each node. This takes O(n) time (not O(n log n) — each node sifts down at most its height, and the sum of heights in a complete binary tree is O(n)).
Phase 2 — Sort: repeat n times: swap the root (maximum) with the last element, reduce heap size by 1, call heapify on the new root. Each heapify call costs O(log n) — total O(n log n).
The O(1) space advantage
Unlike merge sort (O(n) for the merge buffer), heapsort works entirely within the original array. It is the only widely-used sort that guarantees both Θ(n log n) worst case and O(1) extra space. This makes it the fallback in introsort when quicksort's recursion depth is exceeded.
Why Phase 1 is O(n), not O(n log n)
The key insight: leaf nodes (about n/2 of them) never sift down. Nodes at height h sift down at most h steps. The total work = ∑h=0⌊log n⌋ (n/2h+1)⋅h. This geometric sum converges to O(n). Formally: ∑h=0∞ h/2h = 2, so total work ≤ 2n = O(n). CLRS §6.3 proves this rigorously.
Python's heapq: a min-heap
Python's heapq module provides a min-heap (not max-heap). It maintains the heap invariant on a Python list. All operations are O(log n) except heapq.heapify() which is O(n). For a priority queue, use heapq directly. For heapsort, negate values to simulate a max-heap, or use the explicit heapsort above.
import heapq
# Min-heap — smallest element always at index 0
pq = [5, 2, 8, 1, 9]
heapq.heapify(pq) # O(n) — turns list into heap in-place
print(heapq.heappop(pq)) # 1 — extract minimum
heapq.heappush(pq, 0) # O(log n)
print(heapq.heappop(pq)) # 0
# Simulate max-heap with negated values
max_heap = [-x for x in [5, 2, 8, 1, 9]]
heapq.heapify(max_heap)
print(-heapq.heappop(max_heap)) # 9 — largest elementCache performance vs. quicksort
Despite identical asymptotic complexity, heapsort is typically slower than quicksort in practice. The reason: cache behaviour. Quicksort accesses memory sequentially within each partition — excellent locality. Heapsort's heapify step accesses nodes at indices i, 2i+1, 2i+2 — for large heaps, these jump around memory, causing cache misses. Empirically, heapsort runs 2–5× slower than quicksort on random data. Its value is the O(1) space guarantee and O(n log n) worst case, not raw speed.
Formal correctness of heapify
Loop invariant for heapsort phase 2 (CLRS §6.4): at the start of iteration i, arr[i+1..n-1] contains the i largest elements in sorted order, and arr[0..i] is a valid max-heap. Initialisation: after Phase 1, arr[0..n-1] is a max-heap. Maintenance: swapping arr[0] with arr[i] places the maximum at arr[i]; calling heapify restores the max-heap invariant on arr[0..i-1]. Termination: when i=0, the entire array is sorted.
d-ary heaps and Fibonacci heaps
A d-ary heap has d children per node instead of 2. Node at index i has children at di+1, di+2, …, di+d. Heapify costs O(d logd n) = O(d log n / log d). For d=4, heapify is faster in practice (fewer levels, but each heapify step compares more children). Used in some priority queue implementations where decrease-key operations dominate. A Fibonacci heap (Fredman & Tarjan, 1987) achieves O(1) amortised decrease-key and O(log n) amortised delete-min — enabling Dijkstra's algorithm to run in O(V log V + E) vs. O((V+E) log V) with a binary heap.
Cormen, T. H. et al. (2022). CLRS (4th ed.), Ch.6 — Heapsort. Williams, J. W. J. (1964). "Algorithm 232: Heapsort." CACM 7(6). Floyd, R. W. (1964). "Algorithm 245: Treesort 3." CACM 7(12). Fredman, M. & Tarjan, R. (1987). "Fibonacci heaps." JACM 34(3).