Heap Sort Algorithm in DSA Rust

Mental Model

Heap sort turns the list into a special tree structure called a heap, then repeatedly removes the largest item to build a sorted list.

Analogy: Imagine a pile of books stacked so the biggest book is always on top. You take the biggest book off, then rearrange the pile to keep the biggest on top, repeating until all books are sorted.

Array: [4, 10, 3, 5, 1]
Heap tree:
       10
      /  \
     5    3
    / \
   4   1

Dry Run Walkthrough

Input: list: [4, 10, 3, 5, 1]

Goal: Sort the list in ascending order using heap sort

Step 1: Build max heap from array

[10, 5, 3, 4, 1]

Why: We rearrange the array so the largest value is at the root to prepare for sorting

Step 2: Swap root (10) with last element (1), reduce heap size

[1, 5, 3, 4, 10]

Why: Move largest element to its final position at the end

Step 3: Heapify root to restore max heap

[5, 4, 3, 1, 10]

Why: Restore heap property so largest element is at root again

Step 4: Swap root (5) with last element in heap (1), reduce heap size

[1, 4, 3, 5, 10]

Why: Place next largest element in correct position

Step 5: Heapify root to restore max heap

[4, 1, 3, 5, 10]

Why: Restore heap property for remaining elements

Step 6: Swap root (4) with last element in heap (3), reduce heap size

[3, 1, 4, 5, 10]

Why: Place next largest element in correct position

Step 7: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property is already valid here

Step 8: Swap root (3) with last element in heap (1), reduce heap size

[1, 3, 4, 5, 10]

Why: Place next largest element in correct position

Step 9: Heapify root to restore max heap

[1, 3, 4, 5, 10]

Why: Heap property is valid with one element left

Result:

Sorted array: [1, 3, 4, 5, 10]

Annotated Code

DSA Rust

fn heapify(arr: &mut [i32], n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let 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 {
        arr.swap(i, largest); // swap to move largest to root
        heapify(arr, n, largest); // heapify subtree
    }
}

fn heap_sort(arr: &mut [i32]) {
    let n = arr.len();

    // Build max heap
    for i in (0..n / 2).rev() {
        heapify(arr, n, i); // heapify from bottom up
    }

    // Extract elements from heap one by one
    for i in (1..n).rev() {
        arr.swap(0, i); // move current root to end
        heapify(arr, i, 0); // heapify reduced heap
    }
}

fn main() {
    let mut arr = [4, 10, 3, 5, 1];
    heap_sort(&mut arr);
    for val in arr.iter() {
        print!("{} ", val);
    }
    println!();
}

if left < n && arr[left] > arr[largest] { largest = left; }

Check if left child is larger than current largest

if right < n && arr[right] > arr[largest] { largest = right; }

Check if right child is larger than current largest

if largest != i { arr.swap(i, largest); heapify(arr, n, largest); }

Swap root with largest child and heapify subtree

for i in (0..n / 2).rev() { heapify(arr, n, i); }

Build max heap from bottom up

for i in (1..n).rev() { arr.swap(0, i); heapify(arr, i, 0); }

Extract max element and restore heap

Output

1 3 4 5 10 

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n removals takes O(log n) to restore the heap

Space: O(1) because heap sort sorts the array in place without extra storage

vs Alternative: Compared to simple sorts like bubble sort O(n^2), heap sort is much faster for large lists due to efficient heap operations

Edge Cases

empty array

No operations occur, array remains empty

DSA Rust

let n = arr.len();

single element array

Heapify and swaps do nothing, array remains unchanged

DSA Rust

for i in (0..n / 2).rev() { heapify(arr, n, i); }

array with duplicate values

Duplicates are handled normally, sorted output includes duplicates in order

DSA Rust

if left < n && arr[left] > arr[largest]

When to Use This Pattern

When you need to sort in-place with guaranteed O(n log n) time and can use a tree-like structure, heap sort is a strong candidate.

Common Mistakes

Mistake: Not heapifying subtrees after swapping root with largest child
Fix: Call heapify recursively on the affected subtree after swap

Mistake: Building heap from top down instead of bottom up
Fix: Start heapify calls from last non-leaf node down to root

Summary

Heap sort builds a max heap and repeatedly extracts the largest element to sort the array.

Use heap sort when you want an in-place, reliable O(n log n) sorting algorithm without extra memory.

The key insight is maintaining the heap property to efficiently find and remove the largest element each time.

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