Heap Sort Algorithm in DSA Python - 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 builds a max heap, then repeatedly extracts the largest element by swapping root with last, shrinking heap, and heapifying root.

Execution Sample

DSA Python

def heap_sort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

This code builds a max heap from the array, then sorts it by extracting the max repeatedly.

Execution Table

Step	Operation	Heap Size	Array State	Heapify Node	Action
1	Build max heap: heapify at index 1	6	[4, 10, 3, 5, 1, 2]	1	Swap 10 and 1, then heapify child
2	Build max heap: heapify at index 0	6	[10, 5, 3, 4, 1, 2]	0	Swap 10 and 4, then heapify child
3	Build max heap: heapify at index 3	6	[10, 5, 3, 4, 1, 2]	3	No swap needed
4	Extract max: swap root and last	6	[2, 5, 3, 4, 1, 10]	0	Swap 2 and 5, heapify
5	Heapify root	5	[5, 4, 3, 2, 1, 10]	0	Swap 5 and 2, heapify child
6	Heapify index 3	5	[5, 4, 3, 2, 1, 10]	3	No swap needed
7	Extract max: swap root and last	5	[1, 4, 3, 2, 5, 10]	0	Swap 1 and 4, heapify
8	Heapify root	4	[4, 2, 3, 1, 5, 10]	0	Swap 4 and 1, heapify child
9	Heapify index 3	4	[4, 2, 3, 1, 5, 10]	3	No swap needed
10	Extract max: swap root and last	4	[1, 2, 3, 4, 5, 10]	0	Swap 1 and 3, heapify
11	Heapify root	3	[3, 2, 1, 4, 5, 10]	0	Swap 3 and 1
12	Extract max: swap root and last	3	[1, 2, 3, 4, 5, 10]	0	Swap 1 and 2, heapify
13	Heapify root	2	[2, 1, 3, 4, 5, 10]	0	Swap 2 and 1
14	Extract max: swap root and last	2	[1, 2, 3, 4, 5, 10]	0	No swap needed
15	Heap size 1, sorting done	1	[1, 2, 3, 4, 5, 10]	-	Sorted array obtained

💡 Heap size reduced to 1, array is fully sorted

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	After Step 13	Final
arr	[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]
heap_size	6	6	5	4	3	2	1
heapify_node	-	0	0	0	0	0	-

Key Moments - 3 Insights

Why do we start heapify from the middle of the array when building the max heap?

Because nodes after n//2 - 1 are leaves and already satisfy heap property, as shown in execution_table rows 1-3 where heapify starts at index 1 and 0.

Why do we swap the root with the last element during extraction?

Swapping root with last element moves the largest element to its correct sorted position, then heap size reduces, shown in execution_table rows 4, 7, 10, etc.

Why do we heapify only the root after each extraction?

Because only the root may violate max heap after swap, so heapify restores heap property efficiently, as seen in execution_table rows 5, 8, 11.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Array State' column in execution_table row 4.

At which step does the heap size reduce to 3?

A Step 9

B Step 13

C Step 11

D Step 15

💡 Hint

Look at the 'Heap Size' column in execution_table rows.

If we skip heapifying after swapping root and last element, what happens to the array?

A Array remains sorted

B Heap property breaks, array not sorted

C Heap size increases

D No change in array

💡 Hint

Refer to the 'Action' column in execution_table where heapify restores heap property.

Concept Snapshot

Heap Sort Algorithm:
- Build max heap from array (start heapify from middle)
- 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 is done by heapifying nodes starting from the middle of the array towards the root. Once the max heap is built, the largest element is at the root. We swap this root with the last element in the heap, then reduce the heap size by one. After swapping, the heap property may be broken at the root, so we heapify the root to restore the max heap. We repeat this extraction and heapify process until the heap size is reduced to one. The array then becomes sorted in ascending order. The execution table shows each step with array states and heapify actions, and the variable tracker shows how the array and heap size change over time.

Practice

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

easy

A. To reverse the array elements

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

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

D. To count the number of elements in the 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 prepare the array for sorting by ensuring the largest (or smallest) element is at the root.

3. Final Answer:

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

4. Quick Check:

   Heapify = build heap [OK]

Hint: Heapify builds the heap structure before sorting [OK]

Common Mistakes:

• Thinking heapify swaps elements randomly
• Confusing heapify with sorting step
• Assuming heapify counts elements

2. Which of the following is the correct way to call the heapify function in Python for an array arr of size n at index i?

easy

A. heapify(arr, n, i)

B. heapify(i, arr, n)

C. heapify(arr, i, n)

D. heapify(n, i, arr)

Solution

1. Step 1: Recall heapify function signature

   Heapify is usually defined as heapify(array, size, index) to adjust the heap at index.

2. Step 2: Match parameters order

   The correct order is array first, then size, then index to correctly access elements and heap size.

3. Final Answer:

   heapify(arr, n, i) -> Option A

4. Quick Check:

   heapify(array, size, index) = heapify(arr, n, i) [OK]

Hint: Remember: array, size, then index in heapify call [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. What will be the output of the following Python code snippet using heap sort?

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = [4, 10, 3, 5, 1]
heapSort(arr)
print(arr)

medium

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

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

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

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

Solution

1. Step 1: Build max heap from array

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

2. Step 2: Extract elements and heapify

   Swap root with last element and heapify repeatedly to sort ascending: final array is [1, 3, 4, 5, 10]

3. Final Answer:

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

4. Quick Check:

   Heap sort output = sorted array ascending [OK]

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

Common Mistakes:

• Expecting max heap array as final output
• Confusing heapify step with final sort
• Ignoring the swap and heapify loop

4. Identify the error in the following heap sort code snippet:

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l <= n and arr[l] > arr[largest]:
        largest = l
    if r <= n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

medium

A. The condition should be 'l < n' and 'r < n' instead of 'l <= n' and 'r <= n'

B. The swap operation is missing

C. The function should return a value

D. The indices l and r are calculated incorrectly

Solution

1. Step 1: Check index boundary conditions

   Array indices go from 0 to n-1, so conditions must be 'l < n' and 'r < n' to avoid index error.

2. Step 2: Identify impact of wrong condition

   Using 'l <= n' or 'r <= n' can cause index out of range error when l or r equals n.

3. Final Answer:

   The condition should be 'l < n' and 'r < n' instead of 'l <= n' and 'r <= n' -> Option A

4. Quick Check:

   Index check uses less than n, not less or equal [OK]

Hint: Array indices go up to n-1, use '< n' not '<= n' [OK]

Common Mistakes:

• Using <= instead of < for array bounds
• Forgetting to swap elements
• Expecting heapify to return a value

5. Given an array with duplicate elements [4, 10, 4, 5, 1], how does heap sort handle duplicates, and what will be the sorted output?

hard

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

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

C. [1, 4, 5, 10]

D. [4, 4, 5, 10, 1]

Solution

1. Step 1: Understand heap sort with duplicates

   Heap sort treats duplicates as normal values and sorts them in ascending order without removal.

2. Step 2: Sort the array including duplicates

   Sorting [4, 10, 4, 5, 1] results in [1, 4, 4, 5, 10], preserving duplicates in order.

3. Final Answer:

   [1, 4, 4, 5, 10] -> Option B

4. Quick Check:

   Heap sort keeps duplicates, sorts ascending [OK]

Hint: Heap sort keeps duplicates, sorts all elements [OK]

Common Mistakes:

• Assuming duplicates are removed
• Expecting unsorted output with duplicates
• Confusing duplicates with errors