Heap Sort

Category: Classical
Difficulty: Intermediate
Time Complexity: O(n log n)
Space Complexity: O(1)

Overview

Heap Sort first turns the input array into a max-heap, then repeatedly swaps the root (the current maximum) with the last element of the heap region, shrinks the heap by one, and restores the heap property with sift-down. It runs in O(n log n) in every case — best, average, and worst — uses only O(1) auxiliary space, and is in-place but not stable.

Try It

Web: Open in Eigenvue →

Python:

import eigenvue
eigenvue.show("heap-sort")

Default Inputs

{
  "array": [
    3,
    1,
    4,
    1,
    5,
    9,
    2,
    6
  ]
}

Input Examples

Default unsorted

{
  "array": [
    3,
    1,
    4,
    1,
    5,
    9,
    2,
    6
  ]
}

Reverse sorted (worst build)

{
  "array": [
    9,
    8,
    7,
    6,
    5,
    4,
    3,
    2,
    1
  ]
}

Already sorted

{
  "array": [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8
  ]
}

All duplicates

{
  "array": [
    5,
    5,
    5,
    5,
    5
  ]
}

Single element

{
  "array": [
    42
  ]
}

Code

Pseudocode

function heapSort(array):
  n = length(array)
  buildMaxHeap(array, n)
  for heapSize = n down to 2:
    swap array[0] and array[heapSize - 1]
    heapSize = heapSize - 1
    maxHeapify(array, 0, heapSize)

function buildMaxHeap(array, n):
  for i = floor(n / 2) - 1 down to 0:
    maxHeapify(array, i, n)

function maxHeapify(array, i, heapSize):
  left  = 2 * i + 1
  right = 2 * i + 2
  largest = i
  if left  < heapSize and array[left]  > array[largest]:
    largest = left
  if right < heapSize and array[right] > array[largest]:
    largest = right
  if largest != i:
    swap array[i] and array[largest]
    maxHeapify(array, largest, heapSize)

Python

def heap_sort(array: list[int]) -> None:
    n = len(array)
    build_max_heap(array, n)
    heap_size = n
    while heap_size > 1:
        array[0], array[heap_size - 1] = array[heap_size - 1], array[0]
        heap_size -= 1
        max_heapify(array, 0, heap_size)

def build_max_heap(array: list[int], n: int) -> None:
    for i in range(n // 2 - 1, -1, -1):
        max_heapify(array, i, n)

def max_heapify(array: list[int], i: int, heap_size: int) -> None:
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    if left < heap_size and array[left] > array[largest]:
        largest = left
    if right < heap_size and array[right] > array[largest]:
        largest = right
    if largest != i:
        array[i], array[largest] = array[largest], array[i]
        max_heapify(array, largest, heap_size)

JavaScript

function heapSort(array) {
  const n = array.length;
  buildMaxHeap(array, n);
  for (let heapSize = n; heapSize > 1; heapSize--) {
    [array[0], array[heapSize - 1]] = [array[heapSize - 1], array[0]];
    maxHeapify(array, 0, heapSize - 1);
  }
}

function buildMaxHeap(array, n) {
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    maxHeapify(array, i, n);
  }
}

function maxHeapify(array, i, heapSize) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let largest = i;
  if (left < heapSize && array[left] > array[largest]) largest = left;
  if (right < heapSize && array[right] > array[largest]) largest = right;
  if (largest !== i) {
    [array[i], array[largest]] = [array[largest], array[i]];
    maxHeapify(array, largest, heapSize);
  }
}

Key Concepts

Max-heap as an implicit tree

A max-heap is a complete binary tree where every parent is at least as large as its children. We store it inside the input array using index arithmetic — no pointers, no extra nodes. For a node at index i, its parent is at (i−1)/2, its left child at 2i+1, and its right child at 2i+2.

Building the heap takes linear time

It feels like O(n log n) — n nodes, each with a log-n sift — but the work telescopes. Nodes near the leaves vastly outnumber those near the root, and they sift down through far fewer levels. Summing 2^d · (h − d) across depths d gives O(n), not O(n log n). This is the counterintuitive result every learner should sit with.

Sort by repeatedly extracting the max

After build, array[0] is the maximum. Swap it with array[heapSize − 1], shrink heapSize by one, and sift the new root down to restore the heap. The last position is now permanently sorted. Repeat n−1 times and the array is fully sorted in ascending order.

Common Pitfalls

Confusing min-heap and max-heap: Ascending heap-sort uses a max-heap: the largest element bubbles to the root, then gets placed at the end. If you build a min-heap instead, the same algorithm produces a descending sort. The choice of heap kind, not the algorithm structure, fixes the order.
Heap sort is in-place but not stable: Each extraction moves array[0] across the array to the back, jumping over many positions. Equal elements can end up in a different relative order than they started in. If stability matters (e.g., sorting records by a secondary key), use merge sort instead.

Quiz

Q1: For a complete binary tree of n nodes, the maximum height (number of edges from root to a leaf) is:

A) n
B) log₂ n
C) n / 2
D) √n

Show answer

Answer: B) log₂ n

A complete binary tree with n nodes has height ⌊log₂ n⌋. Each sift-down therefore performs at most O(log n) comparisons, which is what makes each extract-max O(log n).

Q2: Why is BUILD-MAX-HEAP O(n) and not O(n log n)?

A) It only touches half of the nodes.
B) Most nodes live near the bottom and have short sift paths; the work, summed across depths, is bounded by a geometric series that telescopes to O(n).
C) It uses fewer comparisons than HEAPSORT does in total.
D) Linear-time build requires an O(n) auxiliary array.