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.