Heap Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Heap Sort Algorithm

Build Max Heap

↓

Heapify from last parent to root

↓

Swap root with last element

↓

Reduce heap size

↓

Heapify root

↓

Repeat swap and heapify until heap size is 1

↓

Sorted Array

Heap Sort first builds a max heap, then repeatedly swaps the root with the last element and heapifies the reduced heap until sorted.

Execution Sample

DSA Javascript

function heapSort(arr) {
  buildMaxHeap(arr);
  for (let end = arr.length - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    heapify(arr, 0, end);
  }
}

This code sorts an array by building a max heap and then sorting by swapping and heapifying.

Execution Table

Step	Operation	Heap Size	Array State	Action/Pointer Changes	Visual State
1	Build Max Heap start	6	[4, 10, 3, 5, 1, 2]	Heapify from index 2 to 0	Initial array as heap
2	Heapify index 2	6	[4, 10, 3, 5, 1, 2]	No change, 3 > children	Heap unchanged
3	Heapify index 1	6	[4, 10, 3, 5, 1, 2]	No swap, 10 > 5 and 1	Heap unchanged
4	Heapify index 0	6	[10, 4, 3, 5, 1, 2]	Swap 4 and 10	Array: [10, 4, 3, 5, 1, 2]
5	Heapify index 1	6	[10, 5, 3, 4, 1, 2]	Swap 4 and 5	Array: [10, 5, 3, 4, 1, 2]
6	Max Heap built	6	[10, 5, 3, 4, 1, 2]	Heap ready	Max heap complete
7	Swap root and end	6	[2, 5, 3, 4, 1, 10]	Swap 10 and 2, reduce size to 5	Array: [2, 5, 3, 4, 1, 10]
8	Heapify root	5	[5, 2, 3, 4, 1, 10]	Swap 2 and 5	Array: [5, 2, 3, 4, 1, 10]
9	Heapify index 1	5	[5, 4, 3, 2, 1, 10]	Swap 2 and 4	Array: [5, 4, 3, 2, 1, 10]
10	Swap root and end	5	[1, 4, 3, 2, 5, 10]	Swap 5 and 1, reduce size to 4	Array: [1, 4, 3, 2, 5, 10]
11	Heapify root	4	[4, 1, 3, 2, 5, 10]	Swap 1 and 4	Array: [4, 1, 3, 2, 5, 10]
12	Heapify index 1	4	[4, 2, 3, 1, 5, 10]	Swap 1 and 2	Array: [4, 2, 3, 1, 5, 10]
13	Swap root and end	4	[1, 2, 3, 4, 5, 10]	Swap 4 and 1, reduce size to 3	Array: [1, 2, 3, 4, 5, 10]
14	Heapify root	3	[3, 2, 1, 4, 5, 10]	Swap 1 and 3	Array: [3, 2, 1, 4, 5, 10]
15	Swap root and end	3	[1, 2, 3, 4, 5, 10]	Swap 3 and 1, reduce size to 2	Array: [1, 2, 3, 4, 5, 10]
16	Heapify root	2	[2, 1, 3, 4, 5, 10]	Swap 1 and 2	Array: [2, 1, 3, 4, 5, 10]
17	Swap root and end	2	[1, 2, 3, 4, 5, 10]	Swap 2 and 1, reduce size to 1	Array: [1, 2, 3, 4, 5, 10]
18	Heapify root	1	[1, 2, 3, 4, 5, 10]	No heapify needed	Heap size 1, done
19	Sorting complete	1	[1, 2, 3, 4, 5, 10]	All sorted	Final sorted array

💡 Heap size reduced to 1, array fully sorted

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 10	After Step 13	After Step 15	Final
arr	[4, 10, 3, 5, 1, 2]	[10, 4, 3, 5, 1, 2]	[10, 5, 3, 4, 1, 2]	[2, 5, 3, 4, 1, 10]	[1, 4, 3, 2, 5, 10]	[1, 2, 3, 4, 5, 10]	[1, 2, 3, 4, 5, 10]	[1, 2, 3, 4, 5, 10]
heapSize	6	6	6	5	4	3	2	1
root	0	0	0	0	0	0	0	0

Key Moments - 3 Insights

Why do we heapify from the last parent node up to the root when building the max heap?

Heapify from the last parent ensures all subtrees satisfy max heap property before reaching the root, as shown in steps 2 to 5 in the execution_table.

Why do we swap the root with the last element before heapifying again?

Swapping moves the largest element (root) to its correct sorted position at the end, then heapify fixes the heap for the remaining elements, as seen in steps 7 and 8.

Why does the heap size reduce after each swap?

Because the last element is sorted and excluded from the heap, reducing heap size ensures heapify only affects unsorted elements, shown in the heapSize changes in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the array state after swapping the root with the last element?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 7 in the execution_table.

At which step does the heap size reduce from 6 to 5?

A Step 7

B Step 6

C Step 8

D Step 9

💡 Hint

Look at the 'Heap Size' column in the execution_table and variable_tracker.

If we skip heapifying after swapping the root with the last element, what would happen to the array?

A The array would remain sorted

B The array would become reversed

C The max heap property would be violated, causing incorrect sorting

D Nothing changes, heapify is optional

💡 Hint

Refer to the 'Action/Pointer Changes' and 'Visual State' columns after swaps in the execution_table.

Concept Snapshot

Heap Sort Algorithm:
- Build a max heap from the array
- Swap root (max) with last element
- Reduce heap size by 1
- Heapify root to restore max heap
- Repeat swap and heapify until heap size is 1
- Result: sorted array in ascending order

Full Transcript

Heap Sort works by first building a max heap from the input array. This means arranging the array so that each parent node is larger than its children. We do this by heapifying from the last parent node up to the root. Once the max heap is built, the largest element is at the root (index 0). We swap this root with the last element in the heap, effectively placing the largest element at its correct sorted position. Then we reduce the heap size by one, excluding the sorted element, and heapify the root again to restore the max heap property. We repeat this process of swapping and heapifying until the heap size is 1, meaning the array is fully sorted. The execution table shows each step with the array state and heap size changes. The variable tracker follows the array and heap size over time. Key moments clarify why heapify starts from the last parent, why swapping is necessary, and why heap size reduces. The visual quiz tests understanding of array states and heap size changes during sorting.

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