SortingAlgorithmaka heapsort

Heap Sort

Build a max-heap in place, then repeatedly swap the root to the end and restore the heap.

▶ VisualizePattern: Heap / Priority QueuePractice (6)
Progress

Overview

Heap sort turns the array into a Max-Heap in O(n), then extracts the maximum n times: swap the root with the last unsorted element, shrink the heap by one, and sift the new root down. It runs in O(n log n) in every case, uses O(1) extra space, and is not stable.

It is essentially Selection Sort with a O(log n) "find max" structure. In practice it is 2–3× slower than Quick Sort because sift-down jumps around memory with poor cache locality, so it is rarely the primary sort; its role is as the fallback in introsort (C++ std::sort) guaranteeing O(n log n), and as the tool for top-k / streaming problems via a Priority Queue.

comparisonO(n log n)in-placeunstableheapguaranteed worst case

Intuition

A mental model before the formal terms.

A tournament bracket where the winner (largest) is always at the top. Remove the champion, put the last player at the top, and let them fall down the bracket losing to whoever is bigger until they find their level — only log₂ n matches needed to crown a new champion. Repeat, stacking champions from the back of the array forwards.

How it works

  1. Heapify: for i = n/2 - 1 down to 0, sift a[i] down so the subtree rooted at i satisfies the max-heap property (children of i are 2i + 1 and 2i + 2).
  2. For end = n - 1 down to 1: swap a[0] (the max) with a[end].
  3. Sift the new a[0] down within [0, end) — swap with the larger child while a child is larger.
  4. After the loop, the array is sorted ascending; the sorted suffix grew from the back.

Why it works

Heap property: every node ≥ its children, so the root is the maximum. Sift-down restores the property along one root-to-leaf path in O(height) = O(log n).

Bottom-up heapify costs O(n): a node at height h costs O(h) and there are about n / 2^(h+1) nodes at height h; the sum Σ h / 2^h converges.

Invariant during extraction: a[0..end) is a max-heap and a[end..n) is sorted with every element ≥ everything in the heap. Each step moves the current max to the boundary, extending the sorted suffix.

Recognition

How to tell a problem wants this.

  • A guaranteed O(n log n) sort with O(1) extra memory is required.
  • Only the top k or the k-th element is needed, especially from a stream — build a heap rather than a full sort.
  • Asked to sort using a heap, implement heapify, or explain why heap sort is slower than quick sort in practice.
“k most frequent” → Heap / Priority Queue

Interactive visualization

Play, step, change the input. ← → and space work too.

a
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
heap (array view, size 8)
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/45Start with 8 elements. Heap sort first turns the array into a max-heap in place (a[i]'s children are a[2i+1] and a[2i+2]), then repeatedly extracts the maximum.
Node being siftedChildren comparedSwappedExtracted (final position)
PseudocodeLearn Heap Sort →
1for i in n//2-1 .. 0: siftDown(a, i, n)   # build max-heap
2for end in n-1 .. 1:
3  swap(a[0], a[end])   # move max to the end
4  siftDown(a, 0, end)
5siftDown(a, i, size):
6  while 2i+1 < size:
7    child = larger of 2i+1, 2i+2
8    if a[i] >= a[child]: break
9    swap(a[i], a[child]); i = child
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(1)
Speed

Pseudocode

1for i from n/2 - 1 down to 0: siftDown(a, i, n)
2for end from n - 1 down to 1:
3  swap(a[0], a[end])
4  siftDown(a, 0, end)
5siftDown(a, i, size):
6  while 2i + 1 < size:
7    c = larger child index; if a[c] <= a[i]: break
8    swap(a[i], a[c]); i = c

Implementations

1def heap_sort(a: list[int]) -> None:
2    n = len(a)
3 
41 · Sift-down restores the max-heap property below index i
5    def sift_down(i: int, size: int) -> None:
6        while True:
7            l, r = 2 * i + 1, 2 * i + 2
8            largest = i
9            if l < size and a[l] > a[largest]:
10                largest = l
11            if r < size and a[r] > a[largest]:
12                largest = r
13            if largest == i:
14                return
15            a[i], a[largest] = a[largest], a[i]
16            i = largest
17 
182 · Build the heap bottom-up in O(n)
19    for i in range(n // 2 - 1, -1, -1):
20        sift_down(i, n)
213 · Repeatedly move the max to the end and shrink the heap
22    for end in range(n - 1, 0, -1):
23        a[0], a[end] = a[end], a[0]
24        sift_down(0, end)
Walkthrough
  1. sift_down is a closure over a; while True with return is the Python idiom.
  2. range(n // 2 - 1, -1, -1) counts down from the last internal node to 0; it is empty for n < 2.
  3. range(n - 1, 0, -1) runs end from n - 1 down to 1.
  4. Tuple swaps move the max to the end; the heap is a[:end].
Complexity (this implementation)
time O(n log n) in all cases · space O(1)

heapq is a min-heap in C; using it means either negating keys or accepting descending output. Pure-Python sift-down is slow.

Language notes
  • heapq implements a min-heap on a plain list: heapq.heapify(a) is O(n), heapq.heappop(a) O(log n). Heap sort via heapq: [heappop(h) for _ in range(len(h))] — but it needs O(n) output space.
  • heapq.nlargest(k, a) / nsmallest cover top-k needs without sorting.
  • list.sort() (TimSort) is stable and faster; heap sort in Python is educational.
Common mistakes in this language
  • Forgetting that heapq is a min-heap; negate keys or use nlargest for max behaviour.
  • Writing range(n // 2, 0, -1) and skipping index 0 (the root).
  • Passing n instead of end to sift_down during extraction.
Language differences that matter here
  • Heap orientation: C++ std::priority_queue / std::make_heap are max-heaps by default; Python heapq is a min-heap only; JS/TS have no built-in heap at all — the code above hand-rolls a max-heap in every language for a uniform ascending in-place sort.
  • C++ std::sort_heap gives library heap sort in O(1) extra space; Python heapq heap sort needs a second list (O(n)); JS/TS have no equivalent.
  • Integer division for the parent/child indices: / on ints in C++, // in Python, >> or Math.floor in JS/TS.
  • Heap sort is unstable everywhere; for a stable O(n log n) sort use std::stable_sort, Array.prototype.sort (stable since ES2019) or Python sorted.

Complexity

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(1)

Heapify is O(n); n extractions at O(log n) each. In-place, not stable, not adaptive. Poor cache locality.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Worst-case O(n log n) with O(1) extra space is mandatory (embedded systems, introsort fallback).
  • Top-k / k-th largest from a stream: maintain a size-k heap in O(n log k).
  • Partial sorting — extracting the m largest costs O(n + m log n).
Avoid it when
  • Raw speed on typical data — Quick Sort and TimSort beat it by a constant factor due to cache behaviour.
  • Stability is required.
  • Linked lists (needs index arithmetic).

Alternatives

Quick SortMerge SortSelection SortTimSort
Compare: Quick Sort vs Heap Sort

Common mistakes

  • Starting heapify at n - 1 and sifting up — correct but O(n log n); bottom-up sift-down from n/2 - 1 is O(n).
  • Off-by-one in child indices (2i vs 2i + 1) when mixing 0-based and 1-based conventions.
  • Not shrinking the heap size after each swap, so the sorted suffix gets pulled back into the heap.
  • Building a min-heap and expecting ascending output in place — a min-heap yields descending order with this scheme.

Interview patterns

  • Kth largest element: min-heap of size k.
  • Merge k sorted lists with a heap of heads.
  • Find median from a data stream with two heaps.
  • Task scheduler / top-k frequent: heap over counts.
Interview questions on this
Mock interviews

Example problems

Merge k Sorted ListshardKth Largest Element in an ArraymediumTop K Frequent ElementsmediumKth Largest Element in a StreameasyFind Median from Data StreamhardTask Schedulermedium