Heap Sort Algorithm in DSA Java - 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

Heap sort first builds a max heap from the array, then repeatedly swaps the root with the last element and heapifies the reduced heap until sorted.

Execution Sample

DSA Java

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

Sorts the array using heap sort by building a max heap and extracting max repeatedly.

Execution Table

Step	Operation	Node Visited / Index	Heap Size	Array State	Visual Heap Tree
1	Build Max Heap - heapify	Index 1	5	[4, 10, 3, 5, 1]	4 / \ 10 3 / \ 5 1
2	Heapify at index 1	Index 1	5	[4, 10, 3, 5, 1]	4 / \ 10 3 / \ 5 1
3	Heapify at index 0	Index 0	5	[10, 5, 3, 4, 1]	10 / \ 5 3 / \ 4 1
4	Swap root with last element	Swap index 0 and 4	5	[1, 5, 3, 4, 10]	1 / \ 5 3 / \ 4 10 (sorted)
5	Heapify root	Index 0	4	[5, 4, 3, 1, 10]	5 / \ 4 3 / \ 1 10 (sorted)
6	Swap root with last element	Swap index 0 and 3	4	[1, 4, 3, 5, 10]	1 / \ 4 3 / \ 5 10 (sorted) 5 (sorted)
7	Heapify root	Index 0	3	[4, 1, 3, 5, 10]	4 / \ 1 3 / \ 5 10 (sorted) 5 (sorted)
8	Swap root with last element	Swap index 0 and 2	3	[3, 1, 4, 5, 10]	3 / \ 1 4 / \ 5 10 (sorted) 5 (sorted) 4 (sorted)
9	Heapify root	Index 0	2	[3, 1, 4, 5, 10]	3 / \ 1 4 / \ 5 10 (sorted) 5 (sorted) 4 (sorted)
10	Swap root with last element	Swap index 0 and 1	2	[1, 3, 4, 5, 10]	1 / \ 3 4 / \ 5 10 (sorted) 5 (sorted) 4 (sorted) 3 (sorted)
11	Heapify root	Index 0	1	[1, 3, 4, 5, 10]	1 / \ 3 4 / \ 5 10 (sorted) 5 (sorted) 4 (sorted) 3 (sorted)
12	Heap size 1 reached	-	1	[1, 3, 4, 5, 10]	All elements sorted

💡 Heap size reduced to 1, array fully sorted

Variable 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	1
Root Value	4	10	5	4	3	1

Key Moments - 3 Insights

Why do we heapify from the last parent node up to the root when building the max heap?

Heapify from last parent to root ensures all subtrees satisfy max heap property before reaching the root, as shown in steps 1-3 in the execution_table.

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

Swapping root with last element moves the largest value to its correct sorted position, then heapify fixes the heap for remaining elements, as seen in steps 4 and 5.

Why does the heap size reduce after each swap?

Reducing heap size excludes the sorted elements from heap operations, preventing them from being moved again, shown in the heap size column decreasing each swap.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the array state?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 3 in execution_table.

At which step does the heap size become 2?

A Step 7

B Step 10

C Step 9

D Step 11

💡 Hint

Look at the 'Heap Size' column in execution_table to find when it is 2.

If we did not reduce the heap size after swapping, what would happen?

A The sorted elements could be moved again, breaking the sort

B Heapify would fix the entire array correctly anyway

C The array would remain unsorted

D The heap size would automatically adjust

💡 Hint

Refer to key_moments about why heap size reduces after each swap.

Concept Snapshot

Heap Sort Algorithm:
- Build max heap from array
- Swap root (max) with last element
- Reduce heap size by 1
- Heapify root to fix 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 that each parent node is larger than its children. We do this by heapifying from the last parent node up to the root. Once the max heap is built, the largest element is at the root (index 0). We swap this root with the last element in the heap, effectively moving the largest element to its correct sorted position at the end of the array. Then we reduce the heap size by one to exclude the sorted element and heapify the root again to restore the max heap property. We repeat this swap and heapify process until the heap size is 1, meaning the array is fully sorted. The execution table shows each step with the array state and heap structure. Key moments clarify why we heapify bottom-up, why we swap root with last element, 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 heap in the Heap Sort algorithm?

easy

A. To count the number of elements in the array

B. To store elements in sorted order permanently

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

D. To reverse the array elements

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.

2. Step 2: Role in Heap Sort

   Heap Sort uses a max-heap to quickly find the largest element at the root, then removes it to build the sorted array.

3. Final Answer:

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

4. Quick Check:

   Heap = fast max/min retrieval [OK]

Hint: Heap always keeps largest or smallest element on top [OK]

Common Mistakes:

• Thinking heap stores sorted elements permanently
• Confusing heap with a simple array
• Assuming heap counts elements

2. Which of the following is the correct way to build a max heap from an array in Java?

easy

A. for (int i = 0; i < n; i++) heapify(arr, i, n);

B. for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n);

C. for (int i = n - 1; i >= 0; i--) heapify(arr, i, n);

D. for (int i = 0; i < n / 2; i++) heapify(arr, i, n);

Solution

1. Step 1: Identify heapify starting point

   Heapify must start from the last non-leaf node, which is at index n/2 - 1, moving upwards.

2. Step 2: Loop direction and range

   The loop runs backwards from n/2 - 1 down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

   for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, i, n); -> Option B

4. Quick Check:

   Build heap from last non-leaf node [OK]

Hint: Start heapify from n/2 - 1 down to 0 [OK]

Common Mistakes:

• Starting heapify from 0 upwards
• Heapifying leaf nodes unnecessarily
• Looping in wrong direction

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

   Max heap of [4,10,3,5,1] is [10,5,3,4,1].

2. Step 2: Extract max and heapify repeatedly

   Remove 10, heapify remaining; then 5, then 4, then 3, then 1, resulting in sorted array [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 ascending [OK]

Common Mistakes:

• Confusing max heap array with sorted array
• Forgetting to heapify after extraction
• Assuming heap sort outputs descending by default

4. Identify the error in this heapify method snippet for max heap in Java:

void heapify(int[] arr, int i, int n) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;
  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, largest, n);
  }
}

medium

A. The swap logic is incorrect

B. The recursive call should be heapify(arr, i, n) instead of heapify(arr, largest, n)

C. The indices for left and right children are incorrect

D. The comparison for left child should be '>' instead of '<'

Solution

1. Step 1: Check comparison operators for max heap

   For max heap, parent should be greater than children, so we check if child > parent to update largest.

2. Step 2: Identify incorrect comparison

   The code uses 'arr[left] < arr[largest]' which is wrong; it should be 'arr[left] > arr[largest]'.

3. Final Answer:

   The comparison for left child should be '>' instead of '<' -> Option D

4. Quick Check:

   Max heap needs '>' comparison [OK]

Hint: Max heap compares child > parent [OK]

Common Mistakes:

• Using '<' instead of '>' for max heap
• Wrong recursive call index
• Incorrect child index calculation

5. Given an array with many duplicate elements, how does Heap Sort behave and what is the time complexity in the worst case?

hard

A. Heap Sort handles duplicates normally with O(n log n) worst-case time

B. Heap Sort fails with duplicates and runs in O(n^2)

C. Heap Sort sorts duplicates faster with O(n) time

D. Heap Sort requires extra space for duplicates, increasing complexity

Solution

1. Step 1: Understand duplicates in Heap Sort

   Heap Sort treats duplicates like any other elements; duplicates do not affect the heap property or sorting steps.

2. Step 2: Time complexity with duplicates

   Heap Sort always runs in O(n log n) time in worst case, regardless of duplicates.

3. Final Answer:

   Heap Sort handles duplicates normally with O(n log n) worst-case time -> Option A

4. Quick Check:

   Duplicates do not affect Heap Sort time [OK]

Hint: Duplicates don't change Heap Sort time complexity [OK]

Common Mistakes:

• Thinking duplicates cause slower sorting
• Assuming Heap Sort needs extra space for duplicates
• Confusing Heap Sort with unstable sorts