Heap Sort Algorithm in DSA Rust - Build from Scratch

Heap Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Heap sort is a great way to do this by using a special tree structure called a heap.Imagine you have a messy pile of books and you want to arrange them from smallest to largest by height. Heap sort helps you organize them step by step.

🎯 Goal: Build a Rust program that sorts a list of numbers using the heap sort algorithm. You will create the list, set up helper variables, write the heapify logic, and finally print the sorted list.

📋 What You'll Learn

Create a vector called numbers with the exact values: [4, 10, 3, 5, 1]

Create a variable called n that stores the length of numbers

Write a function called heapify that takes numbers, n, and an index i to maintain the heap property

Use a loop to build the heap from the vector

Use a loop to extract elements from the heap and sort the vector

Print the sorted numbers vector

💡 Why This Matters

🌍 Real World

Heap sort is used in systems where guaranteed O(n log n) sorting time is needed, such as in embedded systems or real-time applications.

💼 Career

Understanding heap sort helps in roles involving algorithm optimization, system programming, and performance-critical software development.

1

Create the initial vector

Create a vector called numbers with these exact values: [4, 10, 3, 5, 1]

DSA Rust

// Create the vector called numbers with the values [4, 10, 3, 5, 1]
// Your code here

Hint

Use let mut numbers = vec![4, 10, 3, 5, 1]; to create the vector.

2

Add the length variable

Create a variable called n that stores the length of the numbers vector

DSA Rust

fn main() {
    let mut numbers = vec![4, 10, 3, 5, 1];
    // Create variable n to store length of numbers
    // Your code here
}

Hint

Use let n = numbers.len(); to get the length.

3

Write the heapify function

Write a function called heapify that takes numbers as a mutable slice, n as usize, and i as usize. It should maintain the max-heap property by comparing the parent and children nodes and swapping if needed.

DSA Rust

fn main() {
    let mut numbers = vec![4, 10, 3, 5, 1];
    let n = numbers.len();
}

// Define heapify function here
// Your code here

Hint

Use recursion to maintain the heap property by swapping the parent with the largest child.

4

Build heap, sort, and print

In main, use a for loop for i in (0..n / 2).rev() to build the heap by calling heapify(&mut numbers, n, i). Then use another for loop for i in (1..n).rev() to swap the first element with numbers[i], call heapify(&mut numbers, i, 0), and finally print the sorted numbers vector.

DSA Rust

fn main() {
    let mut numbers = vec![4, 10, 3, 5, 1];
    let n = numbers.len();

    // Build the heap
    // Your code here

    // Extract elements from heap one by one
    // Your code here

    // Print the sorted vector
    // Your code here
}

fn heapify(numbers: &mut [i32], n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if left  numbers[largest] {
        largest = left;
    }

    if right  numbers[largest] {
        largest = right;
    }

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

Hint

Use two loops: one to build the heap from the middle to the start, and one to extract elements from the heap to sort the vector. Then print the vector.

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