Heap Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Heap Sort

An elegant comparison-based sorting algorithm that organizes data into a binary heap to extract elements in sorted order efficiently and in-place.

How it works

Heap Sort utilizes a binary heap data structure. First, the algorithm transforms the input array into a **Max Heap** where each parent node is greater than or equal to its children. Once the heap is established, the root element (which is guaranteed to be the largest) is swapped with the last element of the array. The active heap size is then reduced by one, and a heapify operation is performed on the root to restore the heap property. This process repeats until the heap is empty, leaving a fully sorted array.

1. Interpret the array as a binary tree.
2. Build a Max Heap in-place starting from the lowest parent node up to the root (index 0).
3. Swap the root (index 0) with the last element of the active unsorted range.
4. Decrease the active unsorted range size by 1.
5. Perform **Heapify** at the root to bubble the new root down to its correct heap position.
6. Repeat steps 3–5 until the active range size is 1.

Complexity

Interactive visualization

Pseudocode

procedure heapSort(A):
  n ← length(A)
  for i from ⌊n/2⌋ − 1 down to 0:
    heapify(A, n, i)
  for i from n − 1 down to 1:
    swap A[0], A[i]
    heapify(A, i, 0)

procedure heapify(A, size, i):
  largest ← i
  left ← 2i + 1
  right ← 2i + 2
  if left < size and A[left] > A[largest]: largest ← left
  if right < size and A[right] > A[largest]: largest ← right
  if largest ≠ i:
    swap A[i], A[largest]
    heapify(A, size, largest)

JavaScript implementation

function heapSort(arr) {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

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

Pros and cons

When to use it

• Systems with hard real-time latency limits: guarantees O(n log n) without Quick Sort's degradation.
• Memory-constrained systems: when O(log n) extra space of Quick Sort or O(n) of Merge Sort cannot be allocated.
• Finding the k-largest elements: can be stopped early after k root extractions, running in O(n + k log n) time.