Build Heap from Array Heapify in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the heap array.

DSA Rust

fn swap(arr: &mut Vec<i32>, i: usize, j: usize) {
    let temp = arr[[1]];
    arr[i] = arr[j];
    arr[j] = temp;
}

Drag options to blanks, or click blank then click option'

Ai

Bj

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong index like 0 or 1 instead of i or j.

We use i to get the element at index i to swap it with the element at index j.

2fill in blank

medium

Complete the code to get the left child index of a node in the heap.

DSA Rust

fn left_child(i: usize) -> usize {
    [1]
}

Drag options to blanks, or click blank then click option'

A2 * i

B2 * i + 1

Ci + 1

Di * 2 - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 2*i instead of 2*i+1 for left child.

The left child of a node at index i in a heap is at 2 * i + 1.

3fill in blank

hard

Fix the error in the heapify function to correctly compare and swap elements.

DSA Rust

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

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

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

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

Drag options to blanks, or click blank then click option'

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of > causes wrong heap structure.

To build a max heap, we swap if the child is greater than the current largest.

4fill in blank

hard

Fill both blanks to complete the build_heap function that heapifies from the bottom up.

DSA Rust

fn build_heap(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in (0..[1]).rev() {
        heapify(arr, n, [2]);
    }
}

Drag options to blanks, or click blank then click option'

An / 2

Bn

Ci

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from n instead of n/2.

Passing n instead of i to heapify.

We start heapifying from the last non-leaf node at index n/2 down to 0, using i as the current index.

5fill in blank

hard

Fill all three blanks to complete the main function that builds a heap and prints it.

DSA Rust

fn main() {
    let mut arr = vec![4, 10, 3, 5, 1];
    [1](&mut arr);
    for [2] in 0..arr.len() {
        print!("{} ", arr[[3]]);
    }
    println!();
}

Drag options to blanks, or click blank then click option'

Abuild_heap

Bi

Dheapify

Attempts:

3 left

💡 Hint

Common Mistakes

Calling heapify directly instead of build_heap.

Using wrong index in print statement.

We call build_heap to create the heap, then print each element using the loop variable i.

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