Heap Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Heap Sort Algorithm

Build Max Heap

↓

Heapify from last parent to root

↓

Swap root with last element

↓

Reduce heap size by 1

↓

Heapify root again

↓

Repeat swap and heapify until heap size is 1

↓

Sorted array ready

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 Go

arr := []int{4, 10, 3, 5, 1}
heapSort(arr)
// Output sorted array

Sorts the array [4, 10, 3, 5, 1] using heap sort algorithm.

Execution Table

Step	Operation	Heap Size	Array State	Heap Visual (Tree)	Notes
1	Build max heap: heapify index 1	5	[4, 10, 3, 5, 1]	4 / \ 10 3 / \ 5 1	Heapify at index 1: children 5 and 1, max child 5 > 10? No, no swap
2	Build max heap: heapify index 0	5	[10, 5, 3, 4, 1]	10 / \ 5 3 / \ 4 1	Swap 4 and 10, then heapify subtree at index 1
3	Heapify index 1 after swap	5	[10, 5, 3, 4, 1]	10 / \ 5 3 / \ 4 1	No further swaps needed
4	Swap root with last element (index 4)	5	[1, 5, 3, 4, 10]	1 / \ 5 3 / \ 4 10	Swap 10 and 1, reduce heap size to 4
5	Heapify root (index 0) with heap size 4	4	[5, 4, 3, 1, 10]	5 / \ 4 3 / \ 1 10	Swap 1 and 5, then heapify index 1
6	Heapify index 1	4	[5, 4, 3, 1, 10]	5 / \ 4 3 / \ 1 10	No swap needed
7	Swap root with last element (index 3)	4	[1, 4, 3, 5, 10]	1 / \ 4 3 / \ 5 10	Swap 5 and 1, reduce heap size to 3
8	Heapify root (index 0) with heap size 3	3	[4, 1, 3, 5, 10]	4 / \ 1 3 / \ 5 10	Swap 1 and 4, then heapify index 1
9	Heapify index 1	3	[4, 1, 3, 5, 10]	4 / \ 1 3 / \ 5 10	No swap needed
10	Swap root with last element (index 2)	3	[3, 1, 4, 5, 10]	3 / \ 1 4 / \ 5 10	Swap 4 and 3, reduce heap size to 2
11	Heapify root (index 0) with heap size 2	2	[3, 1, 4, 5, 10]	3 / \ 1 4 / \ 5 10	No swap needed
12	Swap root with last element (index 1)	2	[1, 3, 4, 5, 10]	1 / \ 3 4 / \ 5 10	Swap 3 and 1, reduce heap size to 1
13	Heapify root (index 0) with heap size 1	1	[1, 3, 4, 5, 10]	1 / \ 3 4 / \ 5 10	Heap size 1, no heapify needed
14	Sorting complete	1	[1, 3, 4, 5, 10]	1 / \ 3 4 / \ 5 10	Array sorted in ascending order

💡 Heap size reduced to 1, array fully sorted

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 10	After Step 12	Final
arr	[4,10,3,5,1]	[10,5,3,4,1]	[1,5,3,4,10]	[1,4,3,5,10]	[3,1,4,5,10]	[1,3,4,5,10]	[1,3,4,5,10]
heapSize	5	5	4	4	3	2	1
rootIndex	N/A	0	0	0	0	0	N/A

Key Moments - 3 Insights

Why do we start heapifying from the last parent node and not from the root?

Because leaf nodes are already heaps. Starting from the last parent ensures all subtrees become max heaps, as shown in steps 1 and 2 where heapify begins at index 1 then index 0.

Why do we swap the root with the last element and then reduce heap size?

The root is the largest element in max heap. Swapping it to the end places it in its correct sorted position. Reducing heap size excludes it from further heapify, as seen in steps 4, 7, 10, and 12.

Why do we heapify the root again after each swap?

Swapping breaks the heap property at root. Heapifying restores max heap structure for the reduced heap, as shown in steps 5, 8, 11.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the heap size after swapping the root with the last element?

A 5

B 4

C 3

D 1

💡 Hint

Check the 'Heap Size' column at step 4 in the execution table.

At which step does the array first become a valid max heap?

A Step 1

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Operation' and 'Array State' columns in steps 1 to 3.

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

A Heap property would break, array not sorted correctly

B It would become a min heap

C It would remain sorted

D Heap size would increase

💡 Hint

Refer to steps 5, 8, and 11 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 arranging the array so the largest value is at the root. We do this by heapifying from the last parent node up to the root. Then, we swap the root with the last element in the heap and reduce the heap size by one, effectively placing the largest element at the end of the array. After each swap, we heapify the root again to maintain the max heap property for the remaining elements. We repeat this process until the heap size is one, at which point the array is fully sorted in ascending order. The execution table shows each step with the array state and heap visual, helping to understand how the heap changes during sorting.

Practice

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

easy

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

B. To store elements in sorted order permanently

C. To reverse the order of elements in the array

D. To count the number of elements in the array

Solution

1. Step 1: Understand heap property

   A heap is a special tree-based structure where the parent node is either greater (max-heap) or smaller (min-heap) than its children, allowing quick access to the largest or smallest element.

2. Step 2: Role in Heap Sort

   Heap Sort uses this property to repeatedly extract the largest element from the heap and place it at the end of the array, sorting the array efficiently.

3. Final Answer:

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

4. Quick Check:

   Heap = fast max/min extraction [OK]

Hint: Heap helps quickly get max/min element for sorting [OK]

Common Mistakes:

• Thinking heap stores sorted elements permanently
• Confusing heap with a simple array
• Believing heap reverses array order

2. Which of the following is the correct way to swap two elements in Go during Heap Sort?

easy

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

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

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

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

Solution

1. Step 1: Understand Go multiple assignment

   Go allows swapping two variables in one line using multiple assignment syntax: arr[i], arr[j] = arr[j], arr[i].

2. Step 2: Check other options

   swap(arr[i], arr[j]) is invalid syntax in Go. arr[i] = arr[j]; arr[j] = arr[i] overwrites arr[i] before assigning arr[j]. temp = arr[i]; arr[j] = arr[i]; arr[i] = temp incorrectly sets arr[j] to old arr[i] and leaves arr[i] unchanged.

3. Final Answer:

   arr[i], arr[j] = arr[j], arr[i] -> Option B

4. Quick Check:

   Go swap uses multiple assignment [OK]

Hint: Use Go's multiple assignment to swap variables [OK]

Common Mistakes:

• Using invalid swap function call
• Overwriting one element before swapping
• Using incorrect temp assignment sequence

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

   Heapify the array to get max heap: [10, 5, 3, 4, 1]

2. Step 2: Extract max and sort

   Repeatedly swap max with last element and heapify remaining: final sorted array is [1, 3, 4, 5, 10]

3. Final Answer:

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

4. Quick Check:

   Heap Sort sorts ascending [OK]

Hint: Heap Sort outputs sorted array in ascending order [OK]

Common Mistakes:

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

4. Identify the bug in this Go heapify function snippet used in Heap Sort:

func heapify(arr []int, n, i int) {
  largest := i
  l := 2*i + 1
  r := 2*i + 2
  if l < n && arr[l] > arr[largest] {
    largest = l
  }
  if r < n && arr[r] > arr[largest] {
    largest = r
  }
  if largest != i {
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, i)
  }
}

medium

A. Swap syntax is invalid in Go

B. Indices l and r are calculated incorrectly

C. Recursive call should be heapify(arr, n, largest) instead of heapify(arr, n, i)

D. Function should return a value

Solution

1. Step 1: Analyze recursive call

   After swapping, heapify must continue from the new largest index to fix subtree, so call should be heapify(arr, n, largest).

2. Step 2: Check other parts

   Indices l and r are correct for binary heap. Swap syntax is valid Go. Function does not need to return value.

3. Final Answer:

   Recursive call should be heapify(arr, n, largest) instead of heapify(arr, n, i) -> Option C

4. Quick Check:

   Recursive call uses largest index [OK]

Hint: After swap, heapify from largest child index [OK]

Common Mistakes:

• Recursing on wrong index after swap
• Miscomputing child indices
• Thinking swap syntax is wrong in Go

5. Given an array with many duplicate values, how does Heap Sort behave compared to Quick Sort in terms of stability and performance?

hard

A. Both Heap Sort and Quick Sort are stable and have same worst-case time

B. Heap Sort is stable and faster than Quick Sort always

C. Quick Sort is stable and always faster than Heap Sort

D. Heap Sort is not stable but has consistent O(n log n) time; Quick Sort is unstable and may degrade to O(n²)

Solution

1. Step 1: Understand stability and time complexity

   Heap Sort is not stable because it swaps elements that may change relative order. It guarantees O(n log n) time always.

2. Step 2: Compare with Quick Sort

   Quick Sort is also not stable and can degrade to O(n²) in worst case, but often faster on average.

3. Final Answer:

   Heap Sort is not stable but has consistent O(n log n) time; Quick Sort is unstable and may degrade to O(n²) -> Option D

4. Quick Check:

   Heap Sort stable? No; Quick Sort worst-case O(n²) [OK]

Hint: Heap Sort always O(n log n), unstable; Quick Sort can be slower [OK]

Common Mistakes:

• Assuming Heap Sort is stable
• Thinking Quick Sort is always faster
• Confusing stability with sorting speed