Home/Sorting/Heap sort
Search algorithmsCTRL K

Heap sort

· selection with a heap · in place
/sorting/heap-sort
COMPARISONS
0
≈ 2 n log₂ n expected
SWAPS
0
sifts plus pops
HEAP
24/ 24
elements still in the heap
PHASE
build
build, then pop n − 1 times
IN PLACE
0/ 24
final positions so far
sifting nodecomparingswappedin place
n = 24 · seed 7 · 317 steps
step 0 / 316
Size24
heap_sort.ts
1
function heapSort(array: number[]) {
2
  const length = array.length;
3
  for (let i = (length >> 1) - 1; i >= 0; i--) siftDown(array, i, length);
4
  for (let end = length - 1; end > 0; end--) {
5
    [array[0], array[end]] = [array[end], array[0]];
6
    siftDown(array, 0, end);
7
  }
8
}
9
function siftDown(array: number[], i: number, size: number) {
10
  while (true) {
11
    const left = 2 * i + 1, right = left + 1;
12
    let largest = i;
13
    if (left < size && array[left] > array[largest]) largest = left;
14
    if (right < size && array[right] > array[largest]) largest = right;
15
    if (largest === i) return;
16
    [array[i], array[largest]] = [array[largest], array[i]];
17
    i = largest;
18
  }
19
}
CURRENT STEP
line 1

Start: 24 values read as a binary tree: the children of i are 2i + 1 and 2i + 2.

// how it works

Understanding Heap sort

heap sort · n log n with no extra memory
01

The idea

Heap sort treats the array as a binary tree stored level by level: the children of index i sit at 2i + 1 and 2i + 2. It first rearranges the array into a max-heap, where every parent is at least as large as its children, so the maximum is at index 0.

Then it repeats n − 1 times: swap the root with the last element of the heap, shrink the heap by one, and sift the new root down until the heap property holds again. Each pop places one value in its final position, from the end backwards.

02

The four stages

1
buildsift down from the last parent to the root
2
poproot ↔ last element, heap shrinks
3
siftparent vs its larger child
4
settlethe popped value is final
03

Complexity

best
O(n log n)sorted input still builds and pops
average
O(n log n)≈ 2 n log₂ n comparisons
worst
O(n log n)guaranteed, unlike quick sort
space
O(1)in place; the heap lives in the array
04

Versus its siblings

COMPARISONS AT N = 1 000
bubble
499,500
insertion
250,000
heap
17,000
quick
13,900
merge
8,700
random input · the extra comparisons are the price of O(1) space
05

Pseudocode

HEAPSORT(array)
  for i ← ⌊n/2⌋ − 1 down to 0: SIFTDOWN(array, i, n)
  for end ← n − 1 down to 1
    swap array[0], array[end]; SIFTDOWN(array, 0, end)
SIFTDOWN(array, i, size)
  while a child of i is larger: swap with the larger child, descend
06

When to use

When you need a guaranteed n log n bound with no extra memory: embedded systems, kernels, and the fallback inside introsort when quick sort degrades.
Partial sorting: the first k pops give the k largest elements in O(n + k log n).
07

Pitfalls

Poor cache behaviour: sift-down jumps across the array, so quick sort beats it by 2 to 3× in practice.
Not stable, and not adaptive: sorted input is no faster.
Building the heap by n inserts is O(n log n); Floyd's bottom-up build is O(n).
08

History

J. W. J. Williams published heap sort in 1964, introducing the binary heap along with it. Robert Floyd improved it the same year with the O(n) bottom-up heap construction shown here, and the algorithm became the safety net of introsort, the sort behind most C++ standard libraries.

Back to Sorting