Build Heap from Array Heapify in DSA Rust - Build from Scratch

Build Heap from Array using Heapify

📖 Scenario: You have a list of numbers representing tasks with different priorities. You want to organize them so the highest priority task is always easy to find. This is done by building a max heap from the list.

🎯 Goal: Build a max heap from an array of numbers using the heapify method. You will write code to rearrange the array so it follows max heap rules.

📋 What You'll Learn

Create a vector called arr with the exact values [3, 9, 2, 1, 4, 5]

Create a variable called n that stores the length of arr

Write a heapify function that takes arr, n, and i (index) and rearranges the subtree rooted at i to maintain max heap property

Use a for loop to call heapify from the last non-leaf node down to the root

Print the final arr after building the max heap

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and efficient sorting algorithms.

💼 Career

Understanding heap data structures is important for software engineering roles involving algorithms and performance optimization.

1

Create the initial array

Create a vector called arr with the exact values [3, 9, 2, 1, 4, 5].

DSA Rust

# Create a vector called arr with values [3, 9, 2, 1, 4, 5]
# Your code here

Hint

Use let mut arr = vec![3, 9, 2, 1, 4, 5]; to create the vector.

2

Create a variable for array length

Create a variable called n that stores the length of arr.

DSA Rust

fn main() {
    let mut arr = vec![3, 9, 2, 1, 4, 5];
    // Create a variable n that stores the length of arr
    // Your code here
}

Hint

Use let n = arr.len(); to get the length of the vector.

3

Write the heapify function and build heap loop

Write a function called heapify that takes arr as a mutable slice, n as usize, and i as usize. It should rearrange the subtree rooted at i to maintain max heap property. Then, use a for loop from (n / 2).wrapping_sub(1) down to 0 to call heapify on arr.

DSA Rust

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

    // Define heapify function here
    // Your code here

    // Build heap using for loop
    // Your code here
}

Hint

Define heapify with parameters arr, n, and i. Use recursion to maintain max heap. Then loop from last non-leaf node down to 0 calling heapify.

4

Print the max heap array

Print the vector arr after building the max heap using println!("{:?}", arr);.

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  arr[largest] {
        largest = left;
    }

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

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

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

    for i in (0..=(n / 2).wrapping_sub(1)).rev() {
        heapify(&mut arr, n, i);
    }

    // Print the max heap array
    // Your code here
}

Hint

Use println!("{:?}", arr); to print the vector.

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