Build Heap from Array Heapify in DSA Rust

Mental Model

We turn an unordered list into a heap by fixing each subtree from the bottom up.

Analogy: Imagine organizing a pile of boxes stacked in rows so that each box is heavier than the boxes below it, starting from the bottom rows and moving upward.

Array: [4, 10, 3, 5, 1]
Index:  0   1   2   3   4
Heap tree:
        4
      /   \
    10     3
   /  \
  5    1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

Goal: Convert the array into a max-heap where each parent is greater than its children

Step 1: Start heapify at index 1 (value 10), check children at indices 3 and 4

Array: [4, 10, 3, 5, 1]
Heap tree:
        4
      /   \
    [10]   3
   /  \
  5    1

Why: We start from the last non-leaf node to ensure subtrees are heaps

Step 2: Compare 10 with children 5 and 1, no swap needed as 10 is largest

Array: [4, 10, 3, 5, 1]
Heap tree:
        4
      /   \
    10     3
   /  \
  5    1

Why: Subtree rooted at index 1 is already a max-heap

Step 3: Heapify at index 0 (value 4), compare with children 10 and 3

Array: [4, 10, 3, 5, 1]
Heap tree:
       [4]
      /   \
    10     3
   /  \
  5    1

Why: We fix the root to maintain max-heap property

Step 4: Swap 4 with largest child 10 at index 1

Array: [10, 4, 3, 5, 1]
Heap tree:
       10
      /   \
    [4]    3
   /  \
  5    1

Why: Parent must be larger than children

Step 5: Heapify at index 1 (value 4), compare with children 5 and 1

Array: [10, 4, 3, 5, 1]
Heap tree:
       10
      /   \
    [4]    3
   /  \
  5    1

Why: Fix subtree after swap

Step 6: Swap 4 with largest child 5 at index 3

Array: [10, 5, 3, 4, 1]
Heap tree:
       10
      /   \
    5      3
   /  \
 [4]   1

Why: Maintain max-heap property in subtree

Step 7: Heapify at index 3 (value 4), no children to compare, stop

Array: [10, 5, 3, 4, 1]
Heap tree:
       10
      /   \
    5      3
   /  \
  4    1

Why: Leaf node reached, heapify complete

Result:

Array: [10, 5, 3, 4, 1]
Heap tree:
       10
      /   \
    5      3
   /  \
  4    1

Annotated Code

DSA Rust

struct MaxHeap {
    data: Vec<i32>,
}

impl MaxHeap {
    fn new(arr: Vec<i32>) -> Self {
        let mut heap = MaxHeap { data: arr };
        let n = heap.data.len();
        // Start from last non-leaf node and heapify each
        for i in (0..=(n / 2).saturating_sub(1)).rev() {
            heap.heapify(i, n);
        }
        heap
    }

    fn heapify(&mut self, i: usize, n: usize) {
        let mut largest = i;
        let left = 2 * i + 1;
        let right = 2 * i + 2;

        if left < n && self.data[left] > self.data[largest] {
            largest = left;
        }

        if right < n && self.data[right] > self.data[largest] {
            largest = right;
        }

        if largest != i {
            self.data.swap(i, largest); // swap parent with largest child
            self.heapify(largest, n);   // recursively heapify affected subtree
        }
    }

    fn print_heap(&self) {
        for val in &self.data {
            print!("{} ", val);
        }
        println!();
    }
}

fn main() {
    let arr = vec![4, 10, 3, 5, 1];
    let heap = MaxHeap::new(arr);
    heap.print_heap();
}

for i in (0..=(n / 2).saturating_sub(1)).rev() {

start heapify from last non-leaf node moving upwards

heap.heapify(i, n);

heapify subtree rooted at index i

if left < n && self.data[left] > self.data[largest] { largest = left; }

find largest among parent and left child

if right < n && self.data[right] > self.data[largest] { largest = right; }

find largest among current largest and right child

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

swap and recursively fix subtree if parent not largest

Output

10 5 3 4 1 

Complexity Analysis

Time: O(n) because heapify is called on n/2 nodes and each call takes O(log n) in worst case but overall sums to O(n)

Space: O(1) because heapify is done in place without extra data structures

vs Alternative: Naive approach inserting elements one by one into heap is O(n log n), so heapify is more efficient

Edge Cases

empty array

heap remains empty without errors

DSA Rust

for i in (0..=(n / 2).saturating_sub(1)).rev() {

single element array

heapify does nothing, array remains same

DSA Rust

for i in (0..=(n / 2).saturating_sub(1)).rev() {

all elements equal

heapify completes without swaps, array unchanged

DSA Rust

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

When to Use This Pattern

When you need to build a heap quickly from an unordered array, use bottom-up heapify to efficiently organize the data.

Common Mistakes

Mistake: Starting heapify from the root instead of the last non-leaf node
Fix: Start heapify from index (n/2 - 1) down to 0 to ensure all subtrees are fixed

Mistake: Not recursively heapifying after a swap
Fix: Call heapify recursively on the swapped child's index to fix subtree

Summary

Builds a max-heap from an unordered array by fixing subtrees from bottom up.

Use when you want to convert an array into a heap efficiently before heap operations.

Start heapify from last non-leaf node and fix subtrees recursively to maintain heap property.

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