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.

Practice

1. What is the main purpose of the heap in the Heap Sort algorithm?

easy

A. To reverse the array elements

B. To store elements in sorted order permanently

C. To count the number of elements in the array

D. To efficiently find and remove the largest (or smallest) element

Solution

1. Step 1: Understand heap property

   A heap is a special tree-based structure that allows quick access to the largest (max-heap) or smallest (min-heap) element.

2. Step 2: Role in Heap Sort

   Heap Sort uses the heap to repeatedly extract the largest element and place it at the end, sorting the array.

3. Final Answer:

   To efficiently find and remove the largest (or smallest) element -> Option D

4. Quick Check:

   Heap = fast max/min access [OK]

Hint: Heap helps quickly get max or min element [OK]

Common Mistakes:

• Thinking heap stores sorted elements permanently
• Confusing heap with simple array storage
• Assuming heap reverses the array

2. Which of the following is the correct way to swap two elements arr[i] and arr[j] in JavaScript during Heap Sort?

easy

A. let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i], arr[j] = arr[j], arr[i];

C. swap(arr[i], arr[j]);

D. arr[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Understand JavaScript swap syntax

   JavaScript does not support tuple unpacking like Python, so swapping requires a temporary variable.

2. Step 2: Check each option

   let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable correctly. arr[i], arr[j] = arr[j], arr[i]; is Python syntax, swap(arr[i], arr[j]); is undefined function, arr[i] = arr[j]; arr[j] = arr[i]; overwrites values incorrectly.

3. Final Answer:

   let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Use temp variable to swap [OK]

Hint: Use temp variable to swap in JS [OK]

Common Mistakes:

• Using Python-style tuple swap in JS
• Calling undefined swap function
• Overwriting values without temp variable

3. What will be the output array after applying Heap Sort on [4, 10, 3, 5, 1]?

medium

A. [1, 3, 4, 5, 10]

B. [10, 5, 4, 3, 1]

C. [1, 4, 3, 5, 10]

D. [5, 10, 4, 3, 1]

Solution

1. Step 1: Understand Heap Sort output

   Heap Sort sorts the array in ascending order by default.

2. Step 2: Sort the array

   Sorting [4, 10, 3, 5, 1] gives [1, 3, 4, 5, 10].

3. Final Answer:

   [1, 3, 4, 5, 10] -> Option A

4. Quick Check:

   Sorted ascending = [1, 3, 4, 5, 10] [OK]

Hint: Heap Sort outputs sorted ascending array [OK]

Common Mistakes:

• Confusing heap structure with final sorted array
• Thinking output is descending by default
• Mixing up original and sorted arrays

4. Identify the error in this Heap Sort snippet:

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

medium

A. Swapping elements is done incorrectly

B. The first for loop should start from Math.floor(n / 2) - 1

C. The second for loop should start from i = 0

D. heapify function is called with wrong parameters

Solution

1. Step 1: Check heap building loop

   The first loop builds the heap and should start from the last non-leaf node at index Math.floor(n / 2) - 1, not Math.floor(n / 2).

2. Step 2: Verify other parts

   The second loop and swapping are correct. heapify parameters are also correct.

3. Final Answer:

   The first for loop should start from Math.floor(n / 2) - 1 -> Option B

4. Quick Check:

   Heap build starts at last non-leaf node [OK]

Hint: Heap build starts at floor(n/2)-1 [OK]

Common Mistakes:

• Starting heap build loop at wrong index
• Incorrect swap logic
• Wrong heapify parameters

5. Given an array [12, 11, 13, 5, 6, 7], how many times will the heapify function be called during the entire Heap Sort process?

hard

A. 6 times

B. 10 times

C. 13 times

D. 15 times

Solution

1. Step 1: Count heapify calls during heap build

   Heap build calls heapify top-level from index floor(n/2)-1=2 down to 0 (3 top-level). For this array, heapify(6,0) recurses once to heapify(6,2), total 4 calls.

2. Step 2: Count heapify calls during sorting

   After building heap, heapify called top-level 5 times (i=5 to 1). Tracing: i=5:2 calls, i=4:2, i=3:2, i=2:2, i=1:1, total 9 calls.

3. Step 3: Total calls

   Total heapify calls = 4 (build) + 9 (sort) = 13.

4. Final Answer:

   13 times -> Option C

5. Quick Check:

   Heapify calls = build + sort + recursive calls = 13 [OK]

Hint: Count build + sort + recursive heapify calls =13 [OK]

Common Mistakes:

• Counting only build or only sort calls
• Ignoring recursive heapify calls
• Assuming heapify called once per element