Challenge - 5 Problems
Heap Mastery Badge
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
What is the state of the max-heap array after extracting the max element?
Consider a max-heap represented as an array: [50, 30, 40, 10, 20]. After extracting the max element (50) and performing bubble down, what is the resulting heap array?
DSA Rust
fn bubble_down(heap: &mut Vec<i32>, mut index: usize) {
let length = heap.len();
loop {
let left = 2 * index + 1;
let right = 2 * index + 2;
let mut largest = index;
if left < length && heap[left] > heap[largest] {
largest = left;
}
if right < length && heap[right] > heap[largest] {
largest = right;
}
if largest == index {
break;
}
heap.swap(index, largest);
index = largest;
}
}
fn extract_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;
bubble_down(heap, 0);
}
Some(max)
}
fn main() {
let mut heap = vec![50, 30, 40, 10, 20];
let max = extract_max(&mut heap);
println!("{:?}", heap);
}Attempts:
2 left
💡 Hint
Remember that after removing the root, the last element moves to the root and then bubbles down to restore max-heap property.
✗ Incorrect
After removing 50, the last element 20 moves to the root. Bubble down compares 20 with its children 30 and 40. The largest child is 40, so swap 20 and 40. Now 20 is at index 2 with children indices out of range, so bubble down stops. The heap becomes [40, 30, 20, 10].
❓ Predict Output
intermediate2:00remaining
What is the min-heap array after extracting the min element and bubbling down?
Given a min-heap array: [5, 10, 15, 20, 25]. After extracting the min element (5) and performing bubble down, what is the resulting heap array?
DSA Rust
fn bubble_down_min(heap: &mut Vec<i32>, mut index: usize) {
let length = heap.len();
loop {
let left = 2 * index + 1;
let right = 2 * index + 2;
let mut smallest = index;
if left < length && heap[left] < heap[smallest] {
smallest = left;
}
if right < length && heap[right] < heap[smallest] {
smallest = right;
}
if smallest == index {
break;
}
heap.swap(index, smallest);
index = smallest;
}
}
fn extract_min(heap: &mut Vec<i32>) -> Option<i32> {
if heap.is_empty() {
return None;
}
let min = heap[0];
let last = heap.pop().unwrap();
if !heap.is_empty() {
heap[0] = last;
bubble_down_min(heap, 0);
}
Some(min)
}
fn main() {
let mut heap = vec![5, 10, 15, 20, 25];
let min = extract_min(&mut heap);
println!("{:?}", heap);
}Attempts:
2 left
💡 Hint
After removing the root, the last element moves to the root and bubbles down to maintain min-heap property.
✗ Incorrect
After removing 5, 25 moves to the root [25, 10, 15, 20]. Bubble down compares 25 with children 10 and 15. The smallest child is 10, so swap 25 and 10 resulting in [10, 25, 15, 20]. Now 25 is at index 1 with left child 20 (right out of bounds). Since 20 < 25, swap resulting in [10, 20, 15, 25]. At index 3, no children, bubble down ends. The heap is [10, 20, 15, 25].
🔧 Debug
advanced2:00remaining
Identify the bug in this bubble down implementation for max-heap
This Rust function is intended to bubble down the root element in a max-heap after extraction. What is the bug causing incorrect heap structure?
DSA Rust
fn bubble_down(heap: &mut Vec<i32>, mut index: usize) {
let length = heap.len();
while index < length {
let left = 2 * index + 1;
let right = 2 * index + 2;
let mut largest = index;
if left < length && heap[left] > heap[largest] {
largest = left;
}
if right < length && heap[right] > heap[largest] {
largest = right;
}
if largest == index {
break;
}
heap.swap(index, largest);
// Missing update of index here
}
}Attempts:
2 left
💡 Hint
Check if the loop variable changes after swapping elements.
✗ Incorrect
After swapping the current index with the largest child, the index must be updated to the child's index to continue bubbling down. Without updating index, the loop either runs infinitely or stops prematurely.
❓ Predict Output
advanced2:00remaining
What is the heap array after extracting max from this heap?
Given the max-heap array: [100, 50, 90, 20, 40, 80, 85], after extracting the max element and bubbling down, what is the resulting heap array?
DSA Rust
fn bubble_down(heap: &mut Vec<i32>, mut index: usize) {
let length = heap.len();
loop {
let left = 2 * index + 1;
let right = 2 * index + 2;
let mut largest = index;
if left < length && heap[left] > heap[largest] {
largest = left;
}
if right < length && heap[right] > heap[largest] {
largest = right;
}
if largest == index {
break;
}
heap.swap(index, largest);
index = largest;
}
}
fn extract_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;
bubble_down(heap, 0);
}
Some(max)
}
fn main() {
let mut heap = vec![100, 50, 90, 20, 40, 80, 85];
let max = extract_max(&mut heap);
println!("{:?}", heap);
}Attempts:
2 left
💡 Hint
After removing 100, last element 85 moves to root. Bubble down swaps with largest child each step.
✗ Incorrect
After removing 100, 85 moves to root. Children are 50 and 90; 90 is larger, so swap 85 and 90. Now 85 is at index 2 with children 80 and no right child. 85 > 80, so no swap. Final heap: [90, 50, 85, 20, 40, 80].
🧠 Conceptual
expert2:00remaining
Why is bubble down necessary after extracting the root in a heap?
After extracting the root element from a heap (min or max), why must we perform the bubble down operation?
Attempts:
2 left
💡 Hint
Think about what happens when the last element replaces the root.
✗ Incorrect
When the root is removed, the last element moves to the root position. This element may be smaller (in max-heap) or larger (in min-heap) than its children, violating the heap property. Bubble down swaps it with the appropriate child until the heap property is restored.