Heap Sort

An in-place max heap shown as both an array and a tree

Turn the array into a priority structure

Heap Sort interprets the array as a complete binary tree. In a max heap, every parent is at least as large as its children, so the root is the maximum. Floyd's build starts at the last internal node and sifts each subtree downward.

Extract the root into the sorted suffix

Swap the root with the last heap element, shrink the heap, then sift the new root down until the max-heap invariant is restored. The array and tree tracks share element IDs, so every structural change stays synchronized.

Input

Run sift-down from node 4 while building the max heap.

1function heapSort(a: number[]): number[] {
const n = a.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
  siftDown(a, i, n);
for (let end = n - 1; end > 0; end--) {
  [a[0], a[end]] = [a[end], a[0]];
  siftDown(a, 0, end);
}
return a;
10}
11function siftDown(a: number[], i: number, size: number) {
while (2 * i + 1 < size) {
  let largest = i;
  const l = 2 * i + 1, r = 2 * i + 2;
  if (a[l] > a[largest]) largest = l;
  if (r < size && a[r] > a[largest]) largest = r;
  if (largest === i) break;
  [a[i], a[largest]] = [a[largest], a[i]];
  i = largest;
}
21}

n10

PhaseBuild heap

heapSize10

left9

right-

largest4

swapCount0

1 / 57

Guaranteed bounds

Floyd heap construction is O(n). The following n - 1 extractions each cost at most O(log n), giving O(n log n) worst-case time and O(1) auxiliary space. Heap Sort is not stable.

Invariant: before each extraction, the active prefix is a max heap and the suffix is already in its final sorted order.

Compare its tree-based selection with Quick Sort partitioning.

Algorithm Visualizer

Heap Sort

Turn the array into a priority structure

Extract the root into the sorted suffix

Guaranteed bounds