Heap sort algorithm in Data Structures Theory - Step-by-Step Execution

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 heap

↓

Repeat extraction until heap empty

↓

Sorted array

Heap sort first builds a max heap, then repeatedly extracts the largest element by swapping it with the last heap element and restoring the heap, until the array is sorted.

Execution Sample

Data Structures Theory

array = [4, 10, 3, 5, 1]
build_max_heap(array)
for i in range(len(array)-1, 0, -1):
  swap(array[0], array[i])
  heapify(array, 0, i)

This code builds a max heap from the array, then sorts it by swapping the root with the last element and heapifying the reduced heap repeatedly.

Analysis Table

Step	Operation	Array State	Heap Size	Action Description
1	Build max heap	[4, 10, 3, 5, 1]	5	Heapify from bottom non-leaf nodes to root
2	Heapify at index 1	[4, 10, 3, 5, 1]	5	No change, subtree already max heap
3	Heapify at index 0	[10, 5, 3, 4, 1]	5	Swap 4 and 10 to fix heap
4	Swap root with last	[1, 5, 3, 4, 10]	5	Move max 10 to end
5	Heapify root	[5, 4, 3, 1, 10]	4	Restore heap property in reduced heap
6	Swap root with last	[1, 4, 3, 5, 10]	4	Move max 5 to sorted position
7	Heapify root	[4, 1, 3, 5, 10]	3	Restore heap property
8	Swap root with last	[3, 1, 4, 5, 10]	3	Move max 4 to sorted position
9	Heapify root	[3, 1, 4, 5, 10]	2	Restore heap property
10	Swap root with last	[1, 3, 4, 5, 10]	2	Move max 3 to sorted position
11	Heapify root	[1, 3, 4, 5, 10]	1	Heap size 1, no heapify needed
12	Swap root with last	[1, 3, 4, 5, 10]	1	Only one element left, sorting done
13	End	[1, 3, 4, 5, 10]	0	Heap empty, array sorted ascending

💡 Heap size reduced to 0, all elements sorted

State Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	Final
array	[4, 10, 3, 5, 1]	[10, 5, 3, 4, 1]	[5, 4, 3, 1, 10]	[4, 1, 3, 5, 10]	[3, 1, 4, 5, 10]	[1, 3, 4, 5, 10]
heap_size	5	5	4	3	2	0

Key Insights - 3 Insights

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

Because leaf nodes are already heaps, starting from bottom non-leaf nodes ensures subtrees become max heaps before fixing higher nodes, as shown in steps 2 and 3.

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 the heap for the remaining elements, as seen in steps 4 and 5.

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 unsorted part, shown in variable 'heap_size' changes.

Visual Quiz - 3 Questions

Look at the execution table at step 3. What change happens to the array?

A No change, heap is already valid

B The last element is removed

C The root 4 is swapped with 10 to fix the heap

D The array is sorted

💡 Hint

Check 'Array State' and 'Action Description' columns at step 3

At which step does the heap size reduce from 5 to 4?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at 'Heap Size' column changes between steps 4 and 5

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

A The heap property breaks, sorting fails

B The array remains sorted

C Heap size increases

D Nothing changes

💡 Hint

Refer to 'Action Description' for heapify steps after swaps in execution table

Concept Snapshot

Heap sort builds a max heap from the array.
Then repeatedly swaps the root (max) with the last element.
Reduces heap size and heapifies root to restore heap.
Repeats until heap is empty.
Result is a sorted array in ascending order.

Full Transcript

Heap sort algorithm first transforms the input array into a max heap by heapifying from bottom non-leaf nodes up to the root. This ensures the largest element is at the root. Then, it repeatedly swaps the root element with the last element in the heap, effectively moving the largest element to its correct sorted position. After each swap, the heap size is reduced by one, excluding the sorted elements, and the heap property is restored by heapifying the root. This process continues until the heap size is zero, resulting in a fully sorted array in ascending order. Key points include building the heap from bottom up, swapping root with last element before heapifying, and reducing heap size after each extraction.

Practice

1. What is the main data structure used in the Heap sort algorithm to organize elements during sorting?

easy

A. Queue

B. Heap

C. Stack

D. Linked List

Solution

1. Step 1: Understand the core structure of Heap sort

   Heap sort organizes elements using a special tree-based structure called a heap.

2. Step 2: Identify the specific heap type used

   Heap sort uses a max heap to repeatedly extract the largest element for sorting.

3. Final Answer:

   Heap -> Option B

4. Quick Check:

   Heap = Heap sort main structure [OK]

Hint: Heap sort always uses a heap structure [OK]

Common Mistakes:

• Confusing heap with queue or stack
• Thinking linked list is used for sorting
• Assuming array is the main structure

2. Which of the following is the correct first step in the Heap sort algorithm?

easy

A. Build a max heap from the input array

B. Sort the array using bubble sort

C. Reverse the array elements

D. Split the array into two halves

Solution

1. Step 1: Identify the initial operation in Heap sort

   The algorithm starts by building a max heap from the unsorted input array.

2. Step 2: Understand why this step is important

   Building a max heap ensures the largest element is at the root, ready for extraction.

3. Final Answer:

   Build a max heap from the input array -> Option A

4. Quick Check:

   First step = Build max heap [OK]

Hint: Heap sort always starts by building a max heap [OK]

Common Mistakes:

• Confusing with other sorting algorithms like bubble sort
• Trying to reverse or split array first
• Skipping heap construction

3. Consider the array [4, 10, 3, 5, 1]. After building the max heap in Heap sort, what is the root element of the heap?

medium

A. 5

B. 4

C. 10

D. 3

Solution

1. Step 1: Build max heap from the array

   Heap sort builds a max heap where the largest element is at the root. For [4, 10, 3, 5, 1], 10 is the largest.

2. Step 2: Confirm root element

   After heapifying, 10 becomes the root element of the max heap.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Max heap root = largest element = 10 [OK]

Hint: Max heap root is always the largest element [OK]

Common Mistakes:

• Choosing first array element as root
• Confusing max heap with min heap
• Not heapifying properly

4. Identify the error in this Heap sort step: "After building the max heap, the algorithm swaps the root with the last element but forgets to heapify the reduced heap."

medium

A. Heapify must be called after each swap to maintain heap property

B. Heap sort does not use heapify at all

C. Swapping root with last element is not part of Heap sort

D. No error, this is correct

Solution

1. Step 1: Understand the Heap sort process after swapping

   After swapping the root with the last element, the heap property may break in the reduced heap.

2. Step 2: Identify the missing step

   Heapify must be called on the reduced heap to restore the max heap property before next extraction.

3. Final Answer:

   Heapify must be called after each swap to maintain heap property -> Option A

4. Quick Check:

   Heapify needed after swap [OK]

Hint: Always heapify after swapping root in Heap sort [OK]

Common Mistakes:

• Skipping heapify after swap
• Thinking swap alone sorts the array
• Confusing heapify with building heap

5. You have an array with many duplicate elements. How does Heap sort handle duplicates during sorting?

hard

A. Duplicates are kept in their original relative order (stable sort)

B. Heap sort removes duplicates automatically

C. Duplicates cause Heap sort to fail

D. Duplicates may change order because Heap sort is not stable

Solution

1. Step 1: Understand stability in sorting algorithms

   A stable sort keeps duplicates in original order; an unstable sort may reorder them.

2. Step 2: Analyze Heap sort stability

   Heap sort is not stable because heap operations can reorder equal elements arbitrarily.

3. Final Answer:

   Duplicates may change order because Heap sort is not stable -> Option D

4. Quick Check:

   Heap sort is unstable, duplicates reorder [OK]

Hint: Heap sort is not stable; duplicates can reorder [OK]

Common Mistakes:

• Assuming Heap sort is stable
• Thinking duplicates cause errors
• Believing duplicates are removed