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, shrinking the heap, and restoring the heap property 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 Property Action	Visual State
1	Build Max Heap	6	[4, 10, 3, 5, 1, 2]	Heapify from last non-leaf nodes	[10, 5, 3, 4, 1, 2]
2	Swap root with last element	6	[2, 5, 3, 4, 1, 10]	Swap 10 with 2	[2, 5, 3, 4, 1, 10]
3	Heapify root	5	[2, 5, 3, 4, 1]	Heapify at index 0	[5, 4, 3, 2, 1, 10]
4	Swap root with last element	5	[1, 4, 3, 2, 5, 10]	Swap 5 with 1	[1, 4, 3, 2, 5, 10]
5	Heapify root	4	[1, 4, 3, 2]	Heapify at index 0	[4, 2, 3, 1, 5, 10]
6	Swap root with last element	4	[1, 2, 3, 4, 5, 10]	Swap 4 with 1	[1, 2, 3, 4, 5, 10]
7	Heapify root	3	[1, 2, 3]	Heapify at index 0	[3, 2, 1, 4, 5, 10]
8	Swap root with last element	3	[1, 2, 3, 4, 5, 10]	Swap 3 with 1	[1, 2, 3, 4, 5, 10]
9	Heapify root	2	[1, 2]	Heapify at index 0	[2, 1, 3, 4, 5, 10]
10	Swap root with last element	2	[1, 2, 3, 4, 5, 10]	Swap 2 with 1	[1, 2, 3, 4, 5, 10]
11	Heapify root	1	[1]	Heap size 1, no heapify	[1, 2, 3, 4, 5, 10]
12	Done	1	[1, 2, 3, 4, 5, 10]	Heap size 1, sorted	[1, 2, 3, 4, 5, 10]

💡 Heap size reduced to 1, array fully sorted

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	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 last non-leaf node?

Because leaf nodes are already heaps of size 1, starting heapify from last non-leaf node ensures all subtrees become max heaps, as shown in Step 1 of execution_table.

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

Swapping moves the largest element (root) to its correct sorted position at the end, then heapify restores heap property for the reduced heap, as seen in Steps 2 and 3.

Why does heap size reduce after each extraction?

Because the last element is fixed in sorted position and excluded from heap operations, reducing heap size ensures heapify only works on unsorted part, shown in variable_tracker 'Heap Size' changes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the array state after heapifying the root?

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

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

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

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

💡 Hint

Check the 'Array State' column at Step 3 in execution_table

At which step does the heap size become 3 according to variable_tracker?

A After Step 1

B After Step 5

C After Step 7

D After Step 3

💡 Hint

Look at 'Heap Size' row in variable_tracker and find when it is 3

If we skip swapping root with last element, how would the array state change at Step 4?

A Array remains unchanged from Step 3

B Heap property breaks and array is unsorted

C Array becomes sorted immediately

D Heap size increases

💡 Hint

Refer to Step 4 in execution_table where swap is crucial for sorting

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 value is at the root. Then, it swaps the root with the last element, effectively placing the largest value at the end of the array. The heap size is reduced by one, excluding the sorted element. Next, heapify is called on the root to restore the max heap property for the remaining elements. This process repeats until only one element remains in the heap, resulting in a fully sorted array. The execution table shows each step with array states and heap actions. Variable tracker follows heap size and array changes. Key moments clarify why heapify starts from last non-leaf node, why swapping is needed, 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 heapify process in the Heap Sort Algorithm?

easy

A. To build a max heap or min heap from an unsorted array

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

C. To reverse the array elements

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy heap property (max or min heap).

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to build the heap before sorting.

3. Final Answer:

   To build a max heap or min heap from an unsorted array -> Option A

4. Quick Check:

   Heapify builds heap = To build a max heap or min heap from an unsorted array [OK]

Hint: Heapify creates heap structure from array [OK]

Common Mistakes:

• Confusing heapify with swapping elements
• Thinking heapify reverses the array
• Assuming heapify counts elements

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

easy

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

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

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

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

Solution

1. Step 1: Recall C swap syntax

   In C, swapping requires a temporary variable to hold one value.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses temp variable correctly; others are invalid in C.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in C = temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; [OK]

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

Common Mistakes:

• Trying Python-style swap syntax in C
• Assigning without temp causing overwrite
• Using undefined swap function

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

medium

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

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

C. [1, 3, 4, 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 sort

   Repeatedly swap max with last element and heapify to get sorted array [1,3,4,5,10].

3. Final Answer:

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

4. Quick Check:

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

Hint: Heap sort outputs sorted ascending array [OK]

Common Mistakes:

• Confusing max heap with sorted array
• Forgetting to heapify after swaps
• Assuming heap sort outputs descending order

4. Identify the error in this heap sort snippet in C:

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) {
    int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
    heapify(arr, n, largest);
  }
}

medium

A. The recursive call to heapify is missing

B. The swap logic is incorrect

C. The base case for recursion is missing

D. Left and right child indices should be 2*i + 1 and 2*i + 2

Solution

1. Step 1: Check child index calculation

   In 0-based arrays, left child = 2*i + 1, right child = 2*i + 2.

2. Step 2: Verify other parts

   Swap and recursion are correct; base case is implicit by condition checks.

3. Final Answer:

   Left and right child indices should be 2*i + 1 and 2*i + 2 -> Option D

4. Quick Check:

   Child indices in 0-based heap = 2*i+1, 2*i+2 [OK]

Hint: Remember 0-based heap child indices [OK]

Common Mistakes:

• Using 1-based indexing formulas in 0-based arrays
• Ignoring recursive heapify call
• Misplacing swap logic

5. Given an array with many duplicate elements, how does heap sort behave compared to quicksort in terms of stability and performance?

hard

A. Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²)

B. Heap sort is stable and faster than quicksort always

C. Heap sort is stable but slower than quicksort in all cases

D. Heap sort and quicksort are both stable and have same worst-case time

Solution

1. Step 1: Understand stability of heap sort

   Heap sort is not stable because it swaps elements without preserving order of equal keys.

2. Step 2: Compare performance with quicksort

   Heap sort guarantees O(n log n) time always; quicksort is faster on average but can degrade to O(n²).

3. Final Answer:

   Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²) -> Option A

4. Quick Check:

   Heap sort stable? No; Time? O(n log n) always [OK]

Hint: Heap sort stable? No; quicksort worst-case O(n²) [OK]

Common Mistakes:

• Assuming heap sort is stable
• Thinking quicksort worst-case is always O(n log n)
• Confusing stability with speed