Heap Sort

Heap sort combines the best properties of selection sort (in-place) and merge sort (O(n log n) guaranteed). It never degrades to O(n²) like quicksort, requires only O(1) auxiliary space, and runs in O(n log n) regardless of input. The trade-off: it is not stable and has worse cache performance than quicksort.

To understand heap sort, you must first understand the heap data structure and the heapify operation.

The Heap Property

A binary heap is a complete binary tree stored in an array where:

Max-heap: every parent is ≥ its children
Min-heap: every parent is ≤ its children

For heap sort, we use a max-heap. In the array representation:

Parent of index i: Math.floor((i - 1) / 2)
Left child of index i: 2 * i + 1
Right child of index i: 2 * i + 2

The maximum element is always at index 0 (the root).

// Heap stored in array — index relationships
const heap = [90, 80, 70, 50, 40, 60, 30, 20, 10];
//             0   1   2   3   4   5   6   7   8

// Tree structure:
//            90 (0)
//           /       //       80 (1)      70 (2)
//      /           /    //   50 (3) 40 (4) 60 (5) 30 (6)
//   /   // 20(7) 10(8)

// Parent of index 3 (50): Math.floor((3-1)/2) = 1 (80) ✓
// Left child of index 1 (80): 2*1+1 = 3 (50) ✓
// Right child of index 1 (80): 2*1+2 = 4 (40) ✓

Heapify Down (Sift Down)

Heapify (also called sift-down or sink) maintains the max-heap property starting at a given node. If a node is smaller than one of its children, swap it with the larger child, then repeat downward.

// Sift node at index i downward to restore max-heap property
// Only considers the subarray arr[0..n-1]
function heapifyDown(arr, n, i) {
  let largest = i;          // assume current node is largest
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  // Check if left child is larger than current largest
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  // Check if right child is larger than current largest
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  // If largest is not the current node, swap and recurse
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapifyDown(arr, n, largest);  // recursively fix the affected subtree
  }
}

// Example: heapify [10, 80, 70] with i=0, n=3
// largest = 0 (10). Left child = arr[1] = 80 > 10 → largest = 1
// Right child = arr[2] = 70 < 80 → largest stays 1
// Swap arr[0] and arr[1]: [80, 10, 70]
// Recurse on i=1: no children within bounds → done

Build Max-Heap in O(n)

To sort, first build a max-heap from the unsorted array. The naive approach calls heapify n times for O(n log n) total. But we can do it in O(n) using a key observation:

Leaf nodes (indices n/2 to n-1) are already valid single-element heaps. Start heapifying from the last non-leaf (index n/2 - 1) and work up to the root.

Heapifying nodes at deeper levels (leaves) is cheap (O(1)), and there are more of them. The math works out to O(n) total — not O(n log n).

function buildMaxHeap(arr) {
  const n = arr.length;
  // Start from last non-leaf node and heapify up to root
  // Last non-leaf index = Math.floor(n/2) - 1
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapifyDown(arr, n, i);
  }
}

// Example: build heap from [4, 10, 3, 5, 1]
// Last non-leaf: Math.floor(5/2)-1 = 1
// i=1: heapify(arr, 5, 1) → left=3(5), right=4(1) → largest=3 → swap arr[1] and arr[3]
//   → [4, 5, 3, 10, 1]... (simplified)
// i=0: heapify(arr, 5, 0) → ... → [10, 5, 3, 4, 1]
buildMaxHeap([4, 10, 3, 5, 1]);
// → [10, 5, 3, 4, 1] (valid max-heap)

The Full Heap Sort Algorithm

With a max-heap built, sorting is straightforward:

Swap the maximum (root, index 0) with the last element — the max is now in its final position
Reduce the heap size by 1 (ignore the sorted element)
Heapify down from the root to restore the heap property
Repeat n-1 times

This extracts the maximum n times, building the sorted array from right to left.

function heapSort(arr) {
  const n = arr.length;

  // Step 1: Build max-heap — O(n)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapifyDown(arr, n, i);
  }

  // Step 2: Extract max one by one — O(n log n)
  for (let i = n - 1; i > 0; i--) {
    // Move current root (maximum) to end of unsorted portion
    [arr[0], arr[i]] = [arr[i], arr[0]];

    // Heapify the reduced heap (exclude the sorted element at arr[i])
    heapifyDown(arr, i, 0);
  }

  return arr;
}

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

heapSort([12, 11, 13, 5, 6, 7]);  // → [5, 6, 7, 11, 12, 13]
heapSort([4, 10, 3, 5, 1]);       // → [1, 3, 4, 5, 10]

heapSort([12,11,13,5,6,7]) → [5,6,7,11,12,13]
heapSort([4,10,3,5,1]) → [1,3,4,5,10]

Step-by-Step Trace

// Trace: heapSort([3, 1, 4, 1, 5])
// n = 5

// BUILD HEAP:
// Start at index 1 (last non-leaf): heapify([3,1,4,1,5], 5, 1)
//   left=3(1), right=4(5) → largest=4 → swap(arr[1],arr[4])
//   → [3, 5, 4, 1, 1]
// i=0: heapify([3,5,4,1,1], 5, 0)
//   left=1(5), right=2(4) → largest=1 → swap(arr[0],arr[1])
//   → [5, 3, 4, 1, 1]
//   recurse on i=1: left=3(1), right=4(1) → nothing to swap
// Max-heap: [5, 3, 4, 1, 1]

// EXTRACT MAX (i=4): swap arr[0] and arr[4]: [1, 3, 4, 1, 5]
//   heapify(arr, 4, 0) on [1,3,4,1,...]: → [4, 3, 1, 1, 5]

// EXTRACT MAX (i=3): swap arr[0] and arr[3]: [1, 3, 1, 4, 5]
//   heapify(arr, 3, 0) on [1,3,1,...]: → [3, 1, 1, 4, 5]

// EXTRACT MAX (i=2): swap arr[0] and arr[2]: [1, 1, 3, 4, 5]
//   heapify(arr, 2, 0) on [1,1,...]: → [1, 1, 3, 4, 5]

// EXTRACT MAX (i=1): swap arr[0] and arr[1]: [1, 1, 3, 4, 5]
// Final: [1, 1, 3, 4, 5] ✓

Comparison with Merge Sort and Quick Sort

Property	Heap Sort	Merge Sort	Quick Sort
Best Case	O(n log n)	O(n log n)	O(n log n)
Average Case	O(n log n)	O(n log n)	O(n log n)
Worst Case	O(n log n)	O(n log n)	O(n²) naive
Space	O(1)	O(n)	O(log n)
Stable	No	Yes	No
Cache Performance	Poor	Good	Excellent
In-place	Yes	No	Yes
Practical Speed	Slower in practice	Medium	Fastest in practice

Why Heap Sort Is Slower in Practice

Heap sort has poor cache performance. The heapify operation accesses array elements at indices like 1, 2, 4, 8 — jumping all over memory. Modern CPUs depend on cache locality to be fast — sequential memory access is dramatically faster than random access.

Quick sort accesses memory sequentially within each partition step, leading to much better cache utilization. That is why quicksort typically beats heap sort by 2–3x in benchmarks despite identical asymptotic complexity.

Heap sort's value is its guaranteed O(n log n) worst case with O(1) space. It is the worst-case fallback in introsort (C++ std::sort).

Tip

Use heap sort when you need an O(n log n) guarantee AND O(1) space AND cannot tolerate quicksort's O(n²) worst case. In practice, use the built-in sort (Tim Sort or introsort) unless you have a specific reason to implement a sort yourself.

Note

Heap sort gives us a useful bonus: an O(n) algorithm for **building a heap** (the first phase). If you ever need a priority queue for n operations and already have all elements upfront, use buildMaxHeap in O(n) instead of inserting one by one (O(n log n)).