Build Heap from Array Heapify in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output array after heapifying?

Given the array [4, 10, 3, 5, 1], what is the array after building a max heap using heapify?

DSA Rust

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

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);
        heapify(arr, n, largest);
    }
}

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

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

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

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

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

💡 Hint

Remember that heapify builds a max heap by ensuring parents are larger than children.

The build_max_heap function starts heapifying from the last parent node down to the root. After heapifying, the array represents a max heap where each parent node is greater than its children. The correct max heap array is [10, 5, 3, 4, 1].

🧠 Conceptual

intermediate

How many times is heapify called when building a heap from an array of size 8?

If you build a max heap from an array of 8 elements using the standard heapify method, how many times is the heapify function called during the build process?

A 7 times

B 3 times

C 8 times

D 4 times

💡 Hint

Heapify is called once for each non-leaf node.

For an array of size 8, the non-leaf nodes are at indices 0 to 3 (4 nodes). The build process calls heapify once for each non-leaf node in the for loop, from i = 3 down to i = 0. Recursive calls may occur inside heapify, but the build function directly calls heapify 4 times.

🔧 Debug

advanced

Identify the bug in this heapify implementation

What error will this Rust heapify code cause when building a max heap?

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);
        heapify(arr, n, largest);
    }
}

A Index out of bounds panic due to incorrect boundary check

B Stack overflow due to infinite recursion

C Compilation error due to mutable borrow

D No error, code runs correctly

💡 Hint

Check the conditions for left and right child indices against n.

The condition uses 'left <= n' and 'right <= n', but valid indices are from 0 to n-1. Using '<=' allows index n access, which is out of bounds and causes a panic.

❓ Predict Output

advanced

What is the array after building a min heap?

Given the array [9, 4, 7, 1, -2, 6, 5], what is the array after building a min heap using heapify?

DSA Rust

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

fn min_heapify(arr: &mut [i32], n: usize, i: usize) {
    let mut smallest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if left < n && arr[left] < arr[smallest] {
        smallest = left;
    }
    if right < n && arr[right] < arr[smallest] {
        smallest = right;
    }
    if smallest != i {
        arr.swap(i, smallest);
        min_heapify(arr, n, smallest);
    }
}

fn main() {
    let mut arr = vec![9, 4, 7, 1, -2, 6, 5];
    build_min_heap(&mut arr);
    println!("{:?}", arr);
}

A [1, -2, 5, 4, 9, 6, 7]

B [1, 4, 5, -2, 9, 6, 7]

C [-2, 1, 5, 9, 4, 6, 7]

D [-2, 1, 6, 4, 9, 7, 5]

💡 Hint

Min heap ensures parent nodes are smaller than children.

After building the min heap, the smallest element -2 is at the root. The heap property is maintained with parents smaller than children. The resulting array is [-2, 1, 5, 9, 4, 6, 7].

🧠 Conceptual

expert

What is the time complexity of building a heap using heapify?

What is the time complexity of building a max heap from an unsorted array of size n using the heapify method?

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

💡 Hint

Consider that heapify is called on nodes at different depths with different costs.

Although heapify on one node can take O(log n), the total cost of building the heap is O(n) because most nodes are near the leaves and require less work. The sum of all heapify calls results in linear time complexity.

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To find the maximum element in the array

B. To sort the array in ascending order

C. To reverse the array elements

D. To rearrange the array elements to satisfy the heap property

Solution

1. Step 1: Understand heap property

   The heap property requires each parent node to be greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements so this property holds for every subtree, starting from the bottom.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option D

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree order to build a heap fast [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max/min element
• Assuming heapify reverses the array

2. Which of the following Rust code snippets correctly calls the heapify function on an array slice arr starting at index i with heap size n?

easy

A. heapify(arr, i, n);

B. heapify(&mut arr, i, n);

C. heapify(&arr, i, n);

D. heapify(arr, &i, &n);

Solution

1. Step 1: Understand Rust borrowing rules

   To modify an array in Rust, pass a mutable reference: &mut arr.

2. Step 2: Check parameter types

   Indices i and n are usually copied values, so pass by value.

3. Final Answer:

   heapify(&mut arr, i, n); -> Option B

4. Quick Check:

   Mutable reference for array + values for indices [OK]

Hint: Use &mut for arrays when modifying in Rust [OK]

Common Mistakes:

• Passing array without &mut causes compile error
• Passing immutable reference &arr when mutation needed
• Passing references for integers unnecessarily

3. Given the Rust code below, what will be the state of the array after calling build_heap(&mut arr)? Assume build_heap calls heapify correctly to build a max-heap.

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

medium

A. [9, 4, 5, 1, 3, 2]

B. [5, 4, 3, 2, 1, 9]

C. [9, 3, 5, 1, 4, 2]

D. [3, 9, 2, 1, 4, 5]

Solution

1. Step 1: Understand build_heap process

   Build_heap calls heapify from last non-leaf node upwards to root, fixing subtree heaps.

2. Step 2: Apply heapify on array [3,9,2,1,4,5]

   Heapify rearranges to max-heap: root is largest, children smaller. Result is [9,4,5,1,3,2].

3. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option A

4. Quick Check:

   Max-heap root 9, children smaller [OK]

Hint: Build heap from bottom up to fix subtrees [OK]

Common Mistakes:

• Assuming array is sorted after build_heap
• Confusing max-heap with min-heap output
• Not applying heapify from last non-leaf node

4. Consider this Rust function snippet for heapify:

fn heapify(arr: &mut [i32], i: usize, n: 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);
    }
}

What is the bug in this code that prevents building a max-heap correctly?

medium

A. The recursive call to heapify uses wrong parameter order

B. The parameters n and i are swapped in the function signature

C. The calculation of left and right child indices is incorrect

D. The function does not check if i is within bounds before accessing arr[i]

Solution

1. Step 1: Examine function signature

   The signature is fn heapify(arr: &mut [i32], i: usize, n: usize).

2. Step 2: Check recursive call

   The recursive call is heapify(arr, n, largest);, which passes n as i and largest as n: wrong parameter order.

3. Final Answer:

   The recursive call to heapify uses wrong parameter order -> Option A

4. Quick Check:

   Recursive call must match signature: arr, i, n [OK]

Hint: Check recursive call matches function parameter order exactly [OK]

Common Mistakes:

• Swapping n and i in recursive call
• Miscalculating child indices
• Ignoring bounds checks for indices

5. You want to build a min-heap from the array [7, 2, 6, 3, 9, 1] using the standard heapify approach. Which modification should you make to the heapify function to correctly build a min-heap instead of a max-heap?

hard

A. Call heapify starting from the root instead of last non-leaf node

B. Swap the left and right child index calculations

C. Change all '>' comparisons to '<' when comparing child and parent values

D. Reverse the array before calling heapify

Solution

1. Step 1: Understand heap property difference

   Max-heap requires parent > children; min-heap requires parent < children.

2. Step 2: Modify comparison operators

   To build min-heap, change comparisons from '>' to '<' so smaller values rise to the top.

3. Final Answer:

   Change all '>' comparisons to '<' when comparing child and parent values -> Option C

4. Quick Check:

   Min-heap uses less-than comparisons [OK]

Hint: Flip comparison signs to switch max-heap to min-heap [OK]

Common Mistakes:

• Swapping child indices does not affect heap type
• Reversing array does not build min-heap
• Starting heapify from root breaks heap building