Heap Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Heap Sort Algorithm

Build Max Heap from array

↓

Extract max element (root)

↓

Swap root with last element

↓

Reduce heap size by 1

↓

Heapify root to restore max heap

↓

Repeat extraction until heap size is 1

↓

Sorted array obtained

Heap sort first builds a max heap from the array, then repeatedly extracts the largest element by swapping the root with the last element and heapifying the root, shrinking the heap each time until sorted.

Execution Sample

DSA C++

void heapSort(int arr[], int n) {
  buildMaxHeap(arr, n);
  for (int i = n - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

This code builds a max heap and then sorts the array by extracting the max repeatedly.

Execution Table

Step	Operation	Heap Size	Array State	Heap Visual (Tree)	Action Details
1	Build Max Heap	6	[4, 10, 3, 5, 1, 2]	4 / \ 10 3 / \ / 5 1 2	Heapify from bottom non-leaf nodes to root
2	Heapify at index 2	6	[4, 10, 3, 5, 1, 2]	4 / \ 10 3 / \ / 5 1 2	No change, 3 is larger than children
3	Heapify at index 1	6	[4, 10, 3, 5, 1, 2]	4 / \ 10 3 / \ / 5 1 2	Swap 10 with 5, then heapify at child
4	Heapify at index 3	6	[4, 10, 3, 5, 1, 2]	4 / \ 10 3 / \ / 5 1 2	Leaf node, no change
5	Heapify at index 0	6	[10, 5, 3, 4, 1, 2]	10 / \ 5 3 / \ / 4 1 2	Swap 4 and 10, heapify children
6	Extract max and swap with last	6	[2, 5, 3, 4, 1, 10]	2 / \ 5 3 / \ / 4 1 10	Swap root 10 with last element 2
7	Heapify root (index 0)	5	[5, 4, 3, 2, 1, 10]	5 / \ 4 3 / \ 2 1	Swap 2 and 5, heapify children
8	Extract max and swap with last	5	[1, 4, 3, 2, 5, 10]	1 / \ 4 3 / \ 2 5 10	Swap root 5 with last element 1
9	Heapify root (index 0)	4	[4, 2, 3, 1, 5, 10]	4 / \ 2 3 / \ 1 5 10	Swap 1 and 4, heapify children
10	Extract max and swap with last	4	[1, 2, 3, 4, 5, 10]	1 / \ 2 3 / \ 4 5 10	Swap root 4 with last element 1
11	Heapify root (index 0)	3	[3, 2, 1, 4, 5, 10]	3 / \ 2 1	Swap 1 and 3, heapify children
12	Extract max and swap with last	3	[1, 2, 3, 4, 5, 10]	1 / \ 2 3	Swap root 3 with last element 1
13	Heapify root (index 0)	2	[2, 1, 3, 4, 5, 10]	2 / \ 1	Swap 1 and 2
14	Extract max and swap with last	2	[1, 2, 3, 4, 5, 10]	1 / \ 2	Swap root 2 with last element 1
15	Heapify root (index 0)	1	[1, 2, 3, 4, 5, 10]	1	Only one element, no heapify needed
16	Sorting complete	1	[1, 2, 3, 4, 5, 10]	1	Heap size 1, array sorted

💡 Heap size reduced to 1, array fully sorted

Variable Tracker

Variable	Start	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
Heap Size	6	6	5	4	3	2	1
Array	[4,10,3,5,1,2]	[10,5,3,4,1,2]	[5,4,3,2,1,10]	[4,2,3,1,5,10]	[3,2,1,4,5,10]	[2,1,3,4,5,10]	[1,2,3,4,5,10]
Root Value	4	10	5	4	3	2	1

Key Moments - 3 Insights

Why do we build the max heap starting from the bottom non-leaf nodes?

Because leaf nodes are already heaps of size 1, starting from bottom non-leaf nodes ensures heap property is fixed from bottom up, as shown in steps 2-5 in the execution_table.

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

Swapping moves the largest element to its correct sorted position at the end, then heapify restores the heap property for the reduced heap, as seen in steps 6 and 7.

Why does heap size reduce after each extraction?

Because the last element is fixed in sorted position and excluded from the heap, reducing heap size ensures heapify only works on the unsorted part, shown in variable_tracker and steps 7, 9, 11, etc.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the root value after swapping?

A 4

B 10

C 2

D 5

💡 Hint

Check the 'Array State' and 'Heap Visual' columns at step 6 in execution_table.

At which step does the heap size become 3?

A Step 9

B Step 11

C Step 13

D Step 15

💡 Hint

Refer to the 'Heap Size' column in execution_table rows.

If we skip heapifying after swapping root with last element, what happens?

A Heap property breaks, sorting fails

B Array remains sorted

C Heap size increases

D Root value stays the same

💡 Hint

Look at the 'Action Details' column in execution_table where heapify restores heap property.

Concept Snapshot

Heap Sort Algorithm:
- Build max heap from array
- Swap root (max) with last element
- Reduce heap size by 1
- Heapify root to restore max heap
- Repeat 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 the largest element is at the root. Then, the root is swapped with the last element in the heap, effectively placing the largest element at the end of the array. The heap size is reduced by one to exclude the sorted element. Next, the heap property is restored by heapifying the root. This process repeats until only one element remains in the heap, resulting in a fully sorted array. The execution table shows each step with the array state and heap structure. The variable tracker follows heap size and array changes. Key moments clarify why heapify is done bottom-up and why heap size reduces. The visual quiz tests understanding of root values, heap size changes, and the importance of heapify. The concept snapshot summarizes the algorithm steps clearly.

Practice

1. What is the main purpose of the heapify operation in the Heap Sort Algorithm?

easy

A. To reverse the array elements

B. To sort the array directly without building a heap

C. To swap the first and last elements of the array

D. To build a max heap or min heap from an unordered array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy the heap property, making the array a max heap or min heap.

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to build the heap before sorting by repeatedly extracting the root.

3. Final Answer:

   To build a max heap or min heap from an unordered array -> Option D

4. Quick Check:

   Heapify builds heap = A [OK]

Hint: Heapify creates heap structure before sorting [OK]

Common Mistakes:

• Thinking heapify sorts the array directly
• Confusing heapify with swapping elements
• Assuming heapify reverses the array

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in C++ during heap sort?

easy

A. arr.swap(i, j);

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

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

D. swap arr[i], arr[j];

Solution

1. Step 1: Recall C++ swap syntax

   The standard way to swap two elements is using the swap() function with parentheses and commas.

2. Step 2: Check each option

   swap(arr[i], arr[j]); uses correct syntax. arr[i] = arr[j]; arr[j] = arr[i]; overwrites values incorrectly. swap arr[i], arr[j]; misses parentheses. arr.swap(i, j); is invalid method call.

3. Final Answer:

   swap(arr[i], arr[j]); -> Option C

4. Quick Check:

   Correct swap syntax = D [OK]

Hint: Use swap() with parentheses and commas in C++ [OK]

Common Mistakes:

• Assigning values instead of swapping
• Missing parentheses in swap function
• Using non-existent swap methods

3. What will be the output array after applying heap sort on arr = [4, 10, 3, 5, 1]? Print the sorted array.

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: Build max heap from array

   Max heap of [4,10,3,5,1] rearranges to [10,5,3,4,1].

2. Step 2: Extract max and heapify repeatedly

   Extract 10, heapify remaining; then 5, then 4, then 3, then 1 results in sorted ascending array [1,3,4,5,10].

3. Final Answer:

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

4. Quick Check:

   Heap sort ascending = [1,3,4,5,10] [OK]

Hint: Heap sort outputs ascending sorted array [OK]

Common Mistakes:

• Confusing max heap with sorted array
• Reading heap array as sorted directly
• Outputting descending order instead

4. Identify the error in this heap sort snippet and choose the correct fix:

void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2*i;
  int right = 2*i + 1;
  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  if (largest != i) {
    swap(arr[i], arr[largest]);
    heapify(arr, n, largest);
  }
}

medium

A. Remove recursive call to heapify

B. Change left and right to 2*i + 1 and 2*i + 2 respectively

C. Change largest initialization to 0

D. Change swap to arr[i] = arr[largest]

Solution

1. Step 1: Check child index calculation

   In 0-based arrays, left child = 2*i + 1, right child = 2*i + 2. Current code uses 2*i and 2*i + 1 which is incorrect.

2. Step 2: Fix child indices

   Changing left and right to 2*i + 1 and 2*i + 2 fixes indexing and prevents out-of-bound errors.

3. Final Answer:

   Change left and right to 2*i + 1 and 2*i + 2 respectively -> Option B

4. Quick Check:

   Child indices = 2*i+1, 2*i+2 [OK]

Hint: Use 0-based indexing: left=2*i+1, right=2*i+2 [OK]

Common Mistakes:

• Using 1-based indexing formulas in 0-based arrays
• Removing recursion breaks heapify
• Incorrect swap assignment instead of swap function

5. Given an array arr = [12, 11, 13, 5, 6, 7], how many times will the heapify function be called during the build heap phase of heap sort?

hard

A. 4 times

B. 3 times

C. 2 times

D. 5 times

Solution

1. Step 1: Understand build heap calls

   Build heap calls heapify from last non-leaf node down to root. For array size 6, last non-leaf node is at index 2 (0-based).

2. Step 2: Count heapify calls

   Heapify called at indices 2, 1, 0 during build heap phase, totaling 3 calls. However, heapify may call itself recursively inside these calls. Counting only initial calls, it's 3.

3. Step 3: Clarify question intent

   If question means initial calls only, answer is 3. If counting recursive calls inside heapify, index 1 and 0 calls may cause extra heapify calls. For this array, heapify at index 1 calls heapify at index 4 (leaf, no call), index 0 calls heapify at index 1 again, so total calls are 4.

4. Final Answer:

   4 times -> Option A

5. Quick Check:

   Build heap calls heapify 3 + 1 recursive = 4 [OK]

Hint: Count initial + recursive heapify calls during build heap [OK]

Common Mistakes:

• Counting only initial calls, ignoring recursion
• Confusing build heap with sorting phase calls
• Misidentifying last non-leaf node index