Heap Sort Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Heap Sort on a small array

What is the output of the following Rust code after performing heap sort on the array?

DSA Rust

fn heapify(arr: &mut [i32], n: usize, i: usize) {
    let mut largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

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

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

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

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);
    }
}

fn main() {
    let mut arr = [4, 10, 3, 5, 1];
    heap_sort(&mut arr);
    println!("{:?}", arr);
}

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

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

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

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

💡 Hint

Remember heap sort sorts the array in ascending order.

Heap sort builds a max heap and then extracts the largest element repeatedly, resulting in a sorted array in ascending order.

🧠 Conceptual

intermediate

Heap Sort Time Complexity Explanation

Which of the following best describes the time complexity of heap sort and why?

A O(n) because heap sort only rearranges elements once.

B O(n^2) because heapify is called n times and each call takes O(n) time.

C O(log n) because heap sort only processes the root element repeatedly.

D O(n log n) because building the heap takes O(n) and each of the n elements is extracted in O(log n) time.

💡 Hint

Consider the cost of building the heap and the cost of extracting elements.

Building the heap takes O(n) time, and extracting each element takes O(log n) time, repeated n times, resulting in O(n log n) overall.

🔧 Debug

advanced

Identify the bug in this heapify function

What error will this Rust heapify function cause when run on an array?

DSA Rust

fn heapify(arr: &mut [i32], n: usize, i: usize) {
    let mut largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

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

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

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

A Index out of bounds panic because l and r can equal n which is outside array range

B No error, function works correctly

C Stack overflow due to infinite recursion

D Type mismatch error due to incorrect variable types

💡 Hint

Check the conditions for l and r compared to n.

The conditions use <= n but valid indices are less than n, so accessing arr[n] causes panic.

❓ Predict Output

advanced

Heap Sort on a reversed array

What is the output of the following Rust code after heap sorting the reversed array?

DSA Rust

fn heapify(arr: &mut [i32], n: usize, i: usize) {
    let mut largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

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

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

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

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);
    }
}

fn main() {
    let mut arr = [9, 7, 5, 3, 1];
    heap_sort(&mut arr);
    println!("{:?}", arr);
}

A [1, 5, 3, 7, 9]

B [9, 7, 5, 3, 1]

C [1, 3, 5, 7, 9]

D [3, 1, 5, 7, 9]

💡 Hint

Heap sort always sorts in ascending order.

Heap sort rearranges the reversed array into ascending order.

🧠 Conceptual

expert

Why is heap sort preferred over quicksort in worst-case scenarios?

Which statement best explains why heap sort is preferred over quicksort when worst-case time complexity matters?

A Heap sort uses less memory than quicksort in all cases.

B Heap sort guarantees O(n log n) worst-case time, while quicksort can degrade to O(n^2) in worst cases.

C Quicksort is always slower than heap sort regardless of input.

D Heap sort is easier to implement than quicksort.

💡 Hint

Consider worst-case time complexities of both algorithms.

Heap sort has a guaranteed O(n log n) worst-case time, while quicksort can degrade to O(n^2) depending on pivot choices.

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