Heap Sort Algorithm in DSA Javascript

Mental Model

Heap sort organizes data into a special tree shape called a heap to find the largest item quickly, then removes it and repeats until sorted.

Analogy: Imagine a tournament where the strongest player always wins and moves to the top. After each round, the winner is removed, and the next strongest player rises to the top until all players are ranked.

Array: [4, 10, 3, 5, 1]
Heap tree:
       10
      /  \
     5    3
    / \
   4   1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

Goal: Sort the array in ascending order using heap sort

Step 1: Build max heap from array

[10, 5, 3, 4, 1]

Why: We rearrange the array so the largest value is at the root (index 0)

Step 2: Swap root (10) with last element (1), reduce heap size

[1, 5, 3, 4, 10]

Why: Move largest element to its correct final position at the end

Step 3: Heapify root to restore max heap

[5, 4, 3, 1, 10]

Why: Fix heap so largest element is again at root for next extraction

Step 4: Swap root (5) with last element in heap (1), reduce heap size

[1, 4, 3, 5, 10]

Why: Place next largest element in correct position

Step 5: Heapify root to restore max heap

[4, 1, 3, 5, 10]

Why: Restore heap property for remaining elements

Step 6: Swap root (4) with last element in heap (3), reduce heap size

[3, 1, 4, 5, 10]

Why: Place next largest element in correct position

Step 7: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property already holds, no change

Step 8: Swap root (3) with last element in heap (1), reduce heap size

[1, 3, 4, 5, 10]

Why: Place next largest element in correct position

Step 9: Heapify root to restore max heap

[1, 3, 4, 5, 10]

Why: Heap property holds, no change

Result:

[1, 3, 4, 5, 10] -- sorted array in ascending order

Annotated Code

DSA Javascript

class HeapSort {
  static heapify(arr, n, i) {
    let largest = i; // Initialize largest as root
    const left = 2 * i + 1; // left child index
    const right = 2 * i + 2; // right child index

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

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

    // If largest is not root
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]]; // swap

      // Recursively heapify the affected subtree
      HeapSort.heapify(arr, n, largest);
    }
  }

  static sort(arr) {
    const n = arr.length;

    // Build max heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      HeapSort.heapify(arr, n, i);
    }

    // One by one extract elements
    for (let i = n - 1; i > 0; i--) {
      // Move current root to end
      [arr[0], arr[i]] = [arr[i], arr[0]];

      // call max heapify on the reduced heap
      HeapSort.heapify(arr, i, 0);
    }
  }
}

// Driver code
const array = [4, 10, 3, 5, 1];
HeapSort.sort(array);
console.log(array.join(", ") + "\n");

if (left < n && arr[left] > arr[largest]) { largest = left; }

Check if left child is larger than current largest

if (right < n && arr[right] > arr[largest]) { largest = right; }

Check if right child is larger than current largest

if (largest !== i) { swap arr[i] and arr[largest]; heapify(arr, n, largest); }

Swap root with largest child and heapify subtree

for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); }

Build max heap from bottom up

for (let i = n - 1; i > 0; i--) { swap arr[0] and arr[i]; heapify(arr, i, 0); }

Extract max element and restore heap

Output

1, 3, 4, 5, 10

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n elements is extracted with O(log n) heapify operations

Space: O(1) because heap sort sorts the array in place without extra storage

vs Alternative: Compared to simple sorts like bubble sort O(n^2), heap sort is much faster for large data sets due to efficient max element extraction

Edge Cases

empty array

No operations happen, output remains empty

DSA Javascript

const n = arr.length; for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { ... }

array with one element

Heapify and sort loops run zero times, array stays the same

DSA Javascript

for (let i = n - 1; i > 0; i--) { ... }

array with duplicate elements

Duplicates are handled normally and remain in sorted order

DSA Javascript

if (left < n && arr[left] > arr[largest]) { ... }

When to Use This Pattern

When you need to sort data efficiently and can use a tree-like structure to repeatedly find the largest or smallest item, reach for heap sort because it guarantees O(n log n) time and sorts in place.

Common Mistakes

Mistake: Not building the max heap before sorting
Fix: Add a loop to heapify all non-leaf nodes before extraction

Mistake: Not reducing heap size after swapping root with last element
Fix: Pass the reduced heap size to heapify to avoid including sorted elements

Summary

Heap sort turns the array into a max heap to repeatedly extract the largest element and sort the array.

Use heap sort when you want an efficient, in-place sorting algorithm with guaranteed O(n log n) time.

The key insight is building a max heap first so the largest element is always at the root for easy extraction.