Build Heap from Array Heapify in DSA Rust - Execution Trace

Concept Flow - Build Heap from Array Heapify

Start with array

↓

Find last non-leaf node

↓

Heapify node

↓

Move to previous node

↓

Repeat heapify until root

↓

Heap built

Start from the last non-leaf node and heapify each node up to the root to build the heap.

Execution Sample

DSA Rust

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

This code builds a max heap from an unsorted array by heapifying nodes from the last non-leaf node up to the root.

Execution Table

Step	Operation	Node Index	Heapify Action	Array State	Visual State
1	Start build_heap	-	-	[4, 10, 3, 5, 1]	4 -> 10 -> 3 -> 5 -> 1 -> null
2	Heapify at index 1	1	Compare with children (5,1), no swap needed (10 largest)	[4, 10, 3, 5, 1]	4 -> 10 -> 3 -> 5 -> 1 -> null (no change)
3	Heapify at index 0	0	Compare with children (10,3), swap with 10	[10, 4, 3, 5, 1]	10 -> 4 -> 3 -> 5 -> 1 -> null
4	Heapify at index 1	1	Compare with children (5,1), swap with 5	[10, 5, 3, 4, 1]	10 -> 5 -> 3 -> 4 -> 1 -> null
5	Heap built	-	-	[10, 5, 3, 4, 1]	10 -> 5 -> 3 -> 4 -> 1 -> null

💡 All non-leaf nodes heapified, array is now a max heap.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
arr	[4, 10, 3, 5, 1]	[4, 10, 3, 5, 1]	[10, 4, 3, 5, 1]	[10, 5, 3, 4, 1]	[10, 5, 3, 4, 1]
i (heapify index)	-	1	0	1	-

Key Moments - 2 Insights

Why do we start heapifying from the last non-leaf node and not from the root?

Because leaf nodes are already heaps by definition. Starting from the last non-leaf node ensures all subtrees below are heapified before their parents, as shown in steps 2 and 3 in the execution_table.

Why do we sometimes heapify the same index more than once?

After swapping a node with its child, the subtree rooted at the child might violate the heap property. So we heapify that child node again, as seen at step 4 where index 1 is heapified again.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after heapifying index 0 at step 3?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 3 in the execution_table.

At which step does the array become a valid max heap?

A Step 2

B Step 3

C Step 5

D Step 4

💡 Hint

Look at the 'Heap built' operation and final array state in the execution_table.

If the initial array was already a max heap, how would the heapify operations change?

A Heapify would swap all nodes anyway.

B No swaps would occur during heapify steps.

C Heapify would only swap leaf nodes.

D Heapify would skip all nodes.

💡 Hint

Refer to the 'Heapify Action' column showing swaps or no swaps.

Concept Snapshot

Build Heap from Array (Heapify):
- Start from last non-leaf node (n/2 -1) down to 0
- Heapify each node to maintain max heap property
- Heapify swaps node with largest child if needed
- Repeat until root is heapified
- Result: array represents a max heap

Full Transcript

To build a max heap from an array, we start heapifying from the last non-leaf node moving up to the root. Each heapify operation compares a node with its children and swaps if the heap property is violated. This process ensures all subtrees become valid heaps, resulting in a max heap represented by the array. The execution table shows the array state and heapify actions step-by-step, confirming the heap is built after all nodes are processed.

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