Heap Concept Structure and Properties in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this max-heap insertion sequence?

Consider a max-heap initially empty. Insert the elements in this order: 10, 4, 15, 20. What is the heap array after all insertions?

DSA Rust

let mut heap = vec![];
heap.push(10);
// heapify up
heap.push(4);
// heapify up
heap.push(15);
// heapify up
heap.push(20);
// heapify up
// Final heap array

A [20, 10, 15, 4]

B [10, 4, 15, 20]

C [15, 10, 4, 20]

D [20, 15, 10, 4]

💡 Hint

Remember max-heap property: parent nodes are always greater than children.

After inserting 10, heap is [10]. Insert 4, heap is [10,4]. Insert 15, heapify up swaps 15 with 10: [15,4,10]. Insert 20, heapify up swaps 20 with 15: [20,15,10,4].

🧠 Conceptual

intermediate

Which property must a binary heap always satisfy?

Select the property that is always true for a binary heap.

A The tree is a complete binary tree and satisfies the heap order property.

B The tree is a full binary tree with all leaves at the same level.

C The tree is a balanced binary search tree.

D The tree is a perfect binary tree with equal number of nodes on left and right.

💡 Hint

Think about shape and order properties separately.

A binary heap must be a complete binary tree (all levels filled except possibly last, filled left to right) and must satisfy the heap order property (parent >= children for max-heap or parent <= children for min-heap).

🔧 Debug

advanced

What error occurs in this Rust code for heap pop?

This Rust code tries to pop the max element from a max-heap stored in a vector. What error will it cause?

DSA Rust

fn pop_max(heap: &mut Vec<i32>) -> Option<i32> {
    if heap.is_empty() {
        return None;
    }
    let max = heap[0];
    let last = heap.pop().unwrap();
    if !heap.is_empty() {
        heap[0] = last;
    }
    let mut i = 0;
    while i < heap.len() {
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        let mut largest = i;
        if left < heap.len() && heap[left] > heap[largest] {
            largest = left;
        }
        if right < heap.len() && heap[right] > heap[largest] {
            largest = right;
        }
        if largest == i {
            break;
        }
        heap.swap(i, largest);
        i = largest;
    }
    Some(max)
}

A Infinite loop when heap has two elements.

B No error, code runs correctly.

C Index out of bounds panic when heap has one element.

D Compile-time error due to mutable borrow.

💡 Hint

Consider what happens when heap has only one element.

If heap has one element, pop() removes it, then code assigns heap[0] = last, but heap is empty now, so heap[0] access causes panic (index out of bounds).

🚀 Application

advanced

How many elements are in a heap after these operations?

Start with an empty min-heap. Insert 5 elements, then remove 2 elements. How many elements remain?

A 0

B 3

C 5

D 2

💡 Hint

Each removal deletes one element.

Insert 5 elements adds 5. Removing 2 elements subtracts 2. Remaining elements = 5 - 2 = 3.

❓ Predict Output

expert

What is the heap array after heapify on this array?

Given the array [3, 9, 2, 1, 4, 5], what is the array after building a max-heap using heapify?

DSA Rust

let mut arr = vec![3, 9, 2, 1, 4, 5];
// heapify process to build max-heap
// final array after heapify

A [9, 4, 5, 1, 3, 2]

B [9, 4, 5, 3, 1, 2]

C [5, 4, 9, 1, 3, 2]

D [9, 3, 5, 1, 4, 2]

💡 Hint

Heapify starts from last non-leaf node and moves upward.

Heapify transforms the array into a max-heap. After heapify, the array is [9, 4, 5, 1, 3, 2].

Practice

1. What is the main property of a max-heap data structure?

easy

A. Every parent node is less than or equal to its children

B. Every parent node is greater than or equal to its children

C. All leaf nodes are at the same level

D. It is a balanced binary search tree

Solution

1. Step 1: Understand max-heap property

   A max-heap requires that each parent node's value is greater than or equal to its children.

2. Step 2: Compare options with definition

   Every parent node is greater than or equal to its children matches the max-heap property exactly; others describe different structures or properties.

3. Final Answer:

   Every parent node is greater than or equal to its children -> Option B

4. Quick Check:

   Max-heap property = parent ≥ children [OK]

Hint: Max-heap means parent is always bigger or equal [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking heap is a binary search tree
• Assuming all leaves are at the same level

2. Which of the following Rust code snippets correctly creates a max-heap using the standard library?

easy

A. let mut heap = std::collections::BinaryHeap::new();

B. let mut heap = std::collections::VecDeque::new();

C. let mut heap = std::collections::HashMap::new();

D. let mut heap = std::collections::BinaryHeap::new(0);

Solution

1. Step 1: Identify Rust heap creation syntax

   Rust's standard max-heap is created using BinaryHeap::new() for an empty heap.

2. Step 2: Check each option

   A: let mut heap = std::collections::BinaryHeap::new(); uses BinaryHeap::new(), which is correct. B: let mut heap = std::collections::VecDeque::new(); uses VecDeque (not a heap). C: uses HashMap (not a heap). D: uses BinaryHeap::new(0) which is invalid syntax since new() takes no arguments.

3. Final Answer:

   let mut heap = std::collections::BinaryHeap::new(); -> Option A

4. Quick Check:

   BinaryHeap::new() creates max-heap [OK]

Hint: Use BinaryHeap::new() to create max-heap in Rust [OK]

Common Mistakes:

• Using VecDeque or HashMap instead of BinaryHeap
• Confusing with capacity initialization
• Passing arguments to BinaryHeap::new()

3. What will be the output of the following Rust code using a max-heap?

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(10);
    heap.push(5);
    heap.push(20);
    println!("{}", heap.pop().unwrap());
}

medium

A. 5

B. None

C. 10

D. 20

Solution

1. Step 1: Understand BinaryHeap behavior

   BinaryHeap in Rust is a max-heap by default, so pop() returns the largest element.

2. Step 2: Trace the pushed values and pop result

   Values pushed: 10, 5, 20. The largest is 20, so pop() returns 20.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Max-heap pop() returns max value 20 [OK]

Hint: pop() returns max value in Rust BinaryHeap [OK]

Common Mistakes:

• Thinking pop() returns smallest value
• Confusing push order with pop order
• Assuming pop() returns None if heap not empty

4. Identify the error in the following Rust code that tries to create a min-heap using BinaryHeap:

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(3);
    heap.push(1);
    heap.push(2);
    println!("{}", heap.peek().unwrap());
}

medium

A. BinaryHeap is a max-heap by default, not min-heap

B. Missing import for min-heap

C. Cannot push integers into BinaryHeap

D. BinaryHeap does not support peek() method

Solution

1. Step 1: Check BinaryHeap default behavior

   Rust's BinaryHeap is a max-heap by default, so peek() returns the largest element, not the smallest.

2. Step 2: Identify why min-heap is not created

   The code pushes 3,1,2 but peek() returns 3 (max), not 1 (min). To create min-heap, a wrapper or Reverse is needed.

3. Final Answer:

   BinaryHeap is a max-heap by default, not min-heap -> Option A

4. Quick Check:

   BinaryHeap default = max-heap, not min-heap [OK]

Hint: BinaryHeap is max-heap by default; use Reverse for min-heap [OK]

Common Mistakes:

• Assuming peek() returns smallest element
• Thinking BinaryHeap can't store integers
• Believing peek() method is missing

5. You want to implement a priority queue in Rust that always returns the smallest element first. Which approach correctly achieves this using the standard library's BinaryHeap?

hard

A. Use Vec and sort it after every insertion

B. Use BinaryHeap directly as it is a min-heap by default

C. Use BinaryHeap with std::cmp::Reverse wrapper for elements

D. Use BinaryHeap and negate all values before pushing

Solution

1. Step 1: Understand BinaryHeap default behavior

   BinaryHeap is a max-heap by default, so it returns the largest element first.

2. Step 2: Find correct way to get min-heap behavior

   Wrapping elements with std::cmp::Reverse reverses ordering, making BinaryHeap behave like a min-heap.

3. Step 3: Evaluate other options

   Use BinaryHeap directly as it is a min-heap by default is wrong because BinaryHeap is max-heap by default. Use Vec and sort it after every insertion is inefficient. Use BinaryHeap and negate all values before pushing is a hack but not recommended.

4. Final Answer:

   Use BinaryHeap with std::cmp::Reverse wrapper for elements -> Option C

5. Quick Check:

   Reverse wrapper makes max-heap behave like min-heap [OK]

Hint: Wrap with Reverse to get min-heap from BinaryHeap [OK]

Common Mistakes:

• Assuming BinaryHeap is min-heap by default
• Sorting Vec after every insertion is inefficient
• Negating values is error-prone and not idiomatic