Heap Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Heap Sort Algorithm

Build Max Heap

↓

Heapify Subtrees

↓

Swap Root with Last Element

↓

Reduce Heap Size

↓

Heapify Root Again

↓

Repeat Until Heap Size is 1

↓

Sorted Array Ready

Start by building a max heap from the array, then repeatedly swap the root with the last element, reduce heap size, and heapify the root until sorted.

Execution Sample

DSA Rust

fn heap_sort(arr: &mut [i32]) {
  let n = arr.len();
  for i in (0..n / 2).rev() { heapify(arr, n, i); }
  for i in (1..n).rev() {
    arr.swap(0, i);
    heapify(arr, i, 0);
  }
}

This code builds a max heap and then sorts the array by swapping and heapifying.

Execution Table

Step	Operation	Array State	Heap Size	Action Detail	Visual State
1	Build max heap: heapify at index 3	[4, 10, 3, 5, 1]	5	Heapify subtree rooted at 3	[4, 10, 3, 5, 1]
2	Build max heap: heapify at index 2	[4, 10, 3, 5, 1]	5	Heapify subtree rooted at 2	[4, 10, 3, 5, 1]
3	Build max heap: heapify at index 1	[4, 10, 3, 5, 1]	5	Swap 10 and 5, heapify subtree	[4, 10, 3, 5, 1]
4	Build max heap: heapify at index 0	[4, 10, 3, 5, 1]	5	Swap 4 and 10, heapify subtree	[10, 5, 3, 4, 1]
5	Swap root with last element	[10, 5, 3, 4, 1]	5	Swap 10 and 1	[1, 5, 3, 4, 10]
6	Heapify root with heap size 4	[1, 5, 3, 4, 10]	4	Swap 1 and 5, heapify subtree	[5, 4, 3, 1, 10]
7	Swap root with last element	[5, 4, 3, 1, 10]	4	Swap 5 and 1	[1, 4, 3, 5, 10]
8	Heapify root with heap size 3	[1, 4, 3, 5, 10]	3	Swap 1 and 4, heapify subtree	[4, 1, 3, 5, 10]
9	Swap root with last element	[4, 1, 3, 5, 10]	3	Swap 4 and 3	[3, 1, 4, 5, 10]
10	Heapify root with heap size 2	[3, 1, 4, 5, 10]	2	No swap needed (root 3 > child 1)	[3, 1, 4, 5, 10]
11	Swap root with last element	[3, 1, 4, 5, 10]	2	Swap 3 and 1	[1, 3, 4, 5, 10]
12	Heapify root with heap size 1	[1, 3, 4, 5, 10]	1	Heap size 1, no action	[1, 3, 4, 5, 10]
13	Sorting complete	[1, 3, 4, 5, 10]	1	Array sorted	[1, 3, 4, 5, 10]

💡 Heap size reduced to 1, array fully sorted

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 10	Final
arr	[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
current_root	N/A	0	0	0	0	N/A

Key Moments - 3 Insights

Why do we start heapifying from the middle of the array (n/2 - 1) when building the max heap?

Because elements after n/2 - 1 are leaves and already satisfy heap property. See execution_table steps 1-4 where heapify starts at index 3 and moves backward.

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

Swapping moves the largest element (root) to its correct sorted position at the end. Then heapify restores heap property for the reduced heap. See execution_table steps 5 and 6.

Why does heapify stop when heap size is 1?

Because a single element is always a valid heap and sorted. See execution_table step 12 where heap size is 1 and no action is needed.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the array state after heapifying at index 0?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 4 in execution_table

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

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look at the 'Heap Size' column in execution_table between steps 4 and 6

If we swap the root with the last element but forget to heapify again, what happens to the array?

A Heap property is broken, sorting fails

B Heap size increases

C Array remains sorted

D Nothing changes

💡 Hint

Refer to execution_table steps 5 and 6 where heapify restores heap property after 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 restore 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 start heapifying from the middle of the array because elements after that are leaves and already satisfy the heap property. After building the max heap, we repeatedly swap the root (largest element) with the last element in the heap, reduce the heap size, and heapify the root again to maintain the heap property. This process continues until the heap size is 1, meaning the array is fully sorted. The execution table shows each step with the array state, heap size, and actions taken. Key moments include why heapify starts at the middle, why we swap before heapifying, and why heapify stops at heap size 1. The visual quiz tests understanding of array states and heap size changes during the process.

Practice

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

easy

A. To count the frequency of elements

B. To store elements in sorted order permanently

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

D. To reverse the order of elements

Solution

1. Step 1: Understand heap property

   A heap is a special tree where the parent node is always larger (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role in Heap Sort

   Heap Sort uses this property to quickly find the largest element at the root, then remove it and rebuild the heap.

3. Final Answer:

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

4. Quick Check:

   Heap = fast max/min extraction [OK]

Hint: Heap root always holds max/min for quick access [OK]

Common Mistakes:

• Thinking heap stores elements sorted permanently
• Confusing heap with simple array or list
• Assuming heap counts element frequency

2. Which of the following Rust code snippets correctly swaps two elements in a vector during Heap Sort?

easy

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

B. vec.swap(i, j);

C. vec.swap_elements(i, j);

D. vec.exchange(i, j);

Solution

1. Step 1: Identify Rust vector swap method

   Rust's standard Vec<T> has a method called swap that exchanges elements at two indices.

2. Step 2: Check method names

   Only vec.swap(i, j); is valid syntax. Others are incorrect or do not exist.

3. Final Answer:

   vec.swap(i, j); -> Option B

4. Quick Check:

   Rust Vec swap method = vec.swap(i, j) [OK]

Hint: Use vec.swap(i, j) to exchange elements in Rust [OK]

Common Mistakes:

• Using assignment instead of swap for exchange
• Calling non-existent methods like swap_elements
• Confusing swap with exchange

3. What will be the output vector after applying Heap Sort on vec = vec![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 vector

   Heap Sort first builds a max heap: [10, 5, 3, 4, 1]

2. Step 2: Extract max and reorder

   Repeatedly swap root with last element and heapify, resulting in sorted ascending vector: [1, 3, 4, 5, 10]

3. Final Answer:

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

4. Quick Check:

   Heap Sort output = sorted ascending [OK]

Hint: Heap Sort outputs sorted ascending array [OK]

Common Mistakes:

• Confusing max heap array with sorted output
• Expecting descending order output
• Not heapifying after swaps

4. Identify the bug in this Rust Heap Sort snippet:

fn heapify(vec: &mut Vec<i32>, n: usize, i: usize) {
    let mut largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;
    if l < n && vec[l] > vec[largest] {
        largest = l;
    }
    if r < n && vec[r] > vec[largest] {
        largest = r;
    }
    if largest != i {
        vec.swap(i, largest);
        heapify(vec, n, largest);
    }
}

fn heap_sort(vec: &mut Vec<i32>) {
    let n = vec.len();
    for i in (0..n/2).rev() {
        heapify(vec, n, i);
    }
    for i in (1..n-1).rev() {
        vec.swap(0, i);
        heapify(vec, i, 0);
    }
}

medium

A. The second for loop should start from n-1, not 1

B. The first for loop should be (0..n/2).rev(), which is correct here

C. The heapify call inside second loop uses wrong parameters

D. The swap method is used incorrectly

Solution

1. Step 1: Check second for loop range

   The second loop should run from n-1 down to 1 inclusive to swap root with last element correctly.

2. Step 2: Identify loop range error

   Current loop is (1..n-1).rev(), which iterates from n-2 down to 1, but Rust ranges exclude upper bound, so it misses n-1.

3. Final Answer:

   The second for loop should start from n-1, not 1 -> Option A

4. Quick Check:

   Loop must cover all indices from n-1 down to 1 [OK]

Hint: Second loop must start at n-1 to cover all elements [OK]

Common Mistakes:

• Using wrong loop range excluding last element
• Misunderstanding Rust range bounds
• Incorrect recursive call parameters

5. Given a vector vec = vec![3, 1, 4, 1, 5, 9, 2, 6, 5], how many times will the heapify function be called during the entire Heap Sort process?

hard

A. Approximately 2 * n calls

B. Exactly n calls

C. Exactly log n calls

D. Approximately n * log n calls

Solution

1. Step 1: Understand heapify calls in Heap Sort

   Heapify is called during building the heap (about n/2 calls) and during sorting (about n * log n calls).

2. Step 2: Total calls estimate

   Overall, heapify is called approximately n * log n times because each extraction requires heapify down the tree height (log n).

3. Final Answer:

   Approximately n * log n calls -> Option D

4. Quick Check:

   Heapify calls scale with n log n [OK]

Hint: Heapify calls grow roughly n log n times [OK]

Common Mistakes:

• Assuming heapify calls equal n only
• Thinking heapify calls are constant log n
• Confusing build heap and sort phases