Heap Sort Algorithm in DSA Javascript - Build from Scratch

Heap Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Heap sort is a great way to do this by using a special tree structure called a heap.Imagine you have a messy pile of books (numbers) and you want to arrange them from smallest to largest quickly. Heap sort helps you do this by organizing the pile so the biggest book is always on top, then taking it out one by one.

🎯 Goal: Build a heap sort algorithm in JavaScript that sorts an array of numbers in ascending order using a max heap.

📋 What You'll Learn

Create an array called arr with the exact numbers: 12, 11, 13, 5, 6, 7

Create a variable called n to store the length of arr

Write a function called heapify that maintains the max heap property for a subtree rooted at a given index

Write the main heap sort logic that builds the max heap and sorts the array

Print the sorted array after heap sort completes

💡 Why This Matters

🌍 Real World

Heap sort is used in systems where guaranteed O(n log n) sorting time is needed, such as in embedded systems or real-time applications.

💼 Career

Understanding heap sort helps in technical interviews and improves your grasp of efficient sorting algorithms used in software development.

1

Create the initial array

Create an array called arr with these exact numbers: 12, 11, 13, 5, 6, 7.

DSA Javascript

# Your code here

Hint

Use const arr = [...] with the exact numbers inside the square brackets.

2

Create a variable for array length

Create a variable called n and set it to the length of the array arr.

DSA Javascript

const arr = [12, 11, 13, 5, 6, 7];
# Your code here

Hint

Use const n = arr.length; to get the array size.

3

Write the heapify function

Write a function called heapify that takes parameters arr, n, and i. It should maintain the max heap property for the subtree rooted at index i in the array arr of size n. Use variables largest, left, and right inside the function. Swap elements if needed and call heapify recursively.

DSA Javascript

const arr = [12, 11, 13, 5, 6, 7];
const n = arr.length;

# Your code here

Hint

Remember to check left and right children and swap if they are bigger than the current node.

4

Implement heap sort and print the sorted array

Write the heap sort logic: first build a max heap by calling heapify for all non-leaf nodes from Math.floor(n / 2) - 1 down to 0. Then extract elements one by one from the heap by swapping the root with the last element and calling heapify on the reduced heap. Finally, print the sorted array arr using console.log(arr).

DSA Javascript

const arr = [12, 11, 13, 5, 6, 7];
const n = arr.length;

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left  arr[largest]) {
        largest = left;
    }

    if (right  arr[largest]) {
        largest = right;
    }

    if (largest !== i) {
        let temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

# Your code here

Hint

Remember to build the max heap first, then swap the root with the last element and heapify the reduced heap repeatedly.

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