Build Heap from Array Heapify in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

Heapify rearranges elements to satisfy the heap property, ensuring each parent node is greater (max-heap) or smaller (min-heap) than its children.

intermediate

In the context of building a heap, why do we start heapifying from the last non-leaf node?

Because leaf nodes already satisfy the heap property, starting from the last non-leaf node ensures all subtrees are heapified bottom-up efficiently.

intermediate

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

The time complexity is O(n), where n is the number of elements in the array.

beginner

Show the Rust function signature for a heapify function that modifies an array slice in place.

fn heapify(arr: &mut [i32], n: usize, i: usize)

beginner

What happens if you heapify a node that already satisfies the heap property?

No changes occur; the function returns quickly because the subtree rooted at that node is already a valid heap.

When building a max-heap from an array, which node index do you start heapifying from?

A The first leaf node

B The root node

C The last non-leaf node

D The middle node

Heapify starts from the last non-leaf node moving upwards to ensure all subtrees satisfy the heap property.

What is the main goal of the heapify function?

A To maintain the heap property in a subtree

B To sort the array

C To find the maximum element

D To reverse the array

Heapify ensures the subtree rooted at a given node satisfies the heap property.

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

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Building a heap using heapify has a linear time complexity O(n).

In Rust, how do you pass an array to a function to modify it in place?

A By value

B By mutable reference

C By immutable reference

D By copying

Passing a mutable reference (&mut) allows the function to modify the array in place.

If a node satisfies the heap property, what does heapify do?

A Swaps it with its child

B Recursively heapifies children

C Deletes the node

D Does nothing and returns

Heapify returns immediately if the node already satisfies the heap property.

Explain step-by-step how to build a max-heap from an unsorted array using heapify.

Think about fixing smaller heaps first before the bigger ones.

Describe how the heapify function works internally when called on a node.

Focus on comparisons and recursive calls.

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