Tree Applications

Heap Sort

What is Heap Sort?

Heap Sort sorts an array in place by first turning it into a max-heap — a binary tree where every parent is greater than or equal to its children — and then repeatedly removing the largest element (the root) and placing it at the end of the unsorted region. Because the largest remaining value is always at the root of a max-heap, this naturally produces the array in ascending order, one extraction at a time.

How Does It Work?

A binary heap doesn't need pointers or a separate tree structure at all — it can be stored directly in an array. For a node at index i, its children live at indices 2i+1 and 2i+2, and its parent lives at index floor((i-1)/2). This "implicit tree" is exactly what makes Heap Sort an in-place algorithm: the same array that holds the values also encodes the tree shape.

The algorithm runs in two phases. First, build a max-heap out of the entire array by sifting down every non-leaf node, starting from the last one and working back to the root — this bottom-up approach builds the heap in linear time. Second, repeatedly swap the root with the last element of the current heap, shrink the heap by one, and sift the new root down to restore the heap property. After n-1 extractions, the array is fully sorted.

A max-heap: every parent is ≥ its children, and the largest value sits at the root
95824array: [9, 5, 8, 2, 4] — the same heap, stored flat
Root — always the maximum

Algorithm Steps

  1. Build a max-heap from the array:
    • Starting from the last non-leaf node down to the root, sift each node down so it and its descendants satisfy the heap property
  2. Repeatedly extract the maximum:
    • Swap the root (largest value) with the last element of the current heap
    • Shrink the heap size by one — that swapped element is now in its final sorted position
    • Sift the new root down to restore the max-heap property
  3. Stop once the heap size reaches 1 — the array is fully sorted

Time Complexity

  • Best Case: O(n log n) — building the heap is O(n), and each of the n extractions costs O(log n).
  • Average Case: O(n log n) — same shape of work regardless of the input's initial order.
  • Worst Case: O(n log n) — unlike Quick Sort, there's no pathological input that degrades this.
  • Space Complexity: O(1) — sorting happens in place within the array.

Time Complexity Analysis

Advertisement

Because it needs no extra memory beyond a few variables and never degrades on any input, Heap Sort is a reliable choice when worst-case O(n log n) time and O(1) space both matter — it's what backs priority queues, and shows up in hybrid sorts like introsort, which falls back to Heap Sort when Quick Sort's recursion gets too deep.

Daily DSA Challenge by Scale Engineer

Watch an array become a max-heap, then get sorted one extraction at a time

Speed:1x
Comparisons:
0
Swaps:
0
Generate or enter an array to begin

Array Visualization

Generate or enter an array to begin

Heap as a Tree

The heap view fills in once sorting starts
Internal nodeLeaf nodeRootComparingSwappingSorted (out of heap)

Test Your Knowledge before moving forward!

Heap Sort Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Heap Sort Implementation

// Sifts the node at index i down so it and its descendants satisfy the
// max-heap property, considering only the first heapSize elements.
function siftDown(arr, heapSize, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < heapSize && arr[left] > arr[largest]) largest = left;
  if (right < heapSize && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    siftDown(arr, heapSize, largest);
  }
}

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

  // Phase 1: build a max-heap out of the whole array
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, n, i);
  }

  // Phase 2: repeatedly move the root (current max) to the end
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    siftDown(arr, end, 0); // heap shrinks by one each time
  }

  return arr;
}

// Usage example
heapSort([9, 5, 8, 2, 4, 7]); // [2, 4, 5, 7, 8, 9]

Done With the Learning

Mark Heap Sort as done and view it on your dashboard

Explore Other Tree Topics

Huffman Coding

Decision Trees

Syntax Trees

Tree Diameter

Lowest Common Ancestor

Level-order Traversal

Structure & Properties