Imagine you have a list of tasks with different priorities. You want to always pick the highest priority task quickly and also add new tasks efficiently. Why is a heap better than a sorted array for this?
Think about how much work it takes to keep the list sorted when adding new tasks.
A heap keeps the highest priority element at the top and allows insertion and removal in O(log n) time. A sorted array keeps elements in order but inserting a new element requires shifting many elements, which takes O(n) time.
What is the state of the min-heap after inserting the elements 5, 3, 8, 1 in that order?
use std::collections::BinaryHeap;
fn main() {
let mut heap = BinaryHeap::new();
heap.push(std::cmp::Reverse(5));
heap.push(std::cmp::Reverse(3));
heap.push(std::cmp::Reverse(8));
heap.push(std::cmp::Reverse(1));
let mut result = Vec::new();
while let Some(std::cmp::Reverse(val)) = heap.pop() {
result.push(val);
}
println!("{:?}", result);
}Remember that popping from a min-heap returns elements in ascending order.
The min-heap stores elements so that the smallest is always popped first. After inserting 5, 3, 8, 1, popping all elements returns them sorted ascending: 1, 3, 5, 8.
Consider inserting the number 4 into a sorted array [1, 2, 3, 5, 6]. What is the resulting array?
fn main() {
let mut arr = vec![1, 2, 3, 5, 6];
let pos = arr.iter().position(|&x| x > 4).unwrap_or(arr.len());
arr.insert(pos, 4);
println!("{:?}", arr);
}Think about where 4 fits in the sorted order.
4 fits between 3 and 5, so it is inserted at index 3. The array shifts elements after index 3 to the right to make space.
Look at this Rust code that inserts an element into a sorted vector. What causes the inefficiency?
fn insert_sorted(arr: &mut Vec<i32>, val: i32) {
let mut i = 0;
while i < arr.len() && arr[i] < val {
i += 1;
}
arr.insert(i, val);
}
fn main() {
let mut arr = vec![1, 3, 5, 7];
insert_sorted(&mut arr, 4);
println!("{:?}", arr);
}Consider how many elements must move when inserting in the middle of a vector.
Finding the position with a loop is O(n), and inserting shifts elements to the right, also O(n), so total insertion is O(n). This is inefficient compared to heap insertion.
Explain why a sorted array cannot efficiently support both quick insertion of new elements and quick extraction of the highest priority element, unlike a heap.
Think about the cost of keeping the array sorted when adding new elements.
In a sorted array, extracting the highest priority element is fast (O(1)) because it is at one end. But inserting a new element requires shifting elements to keep order, which takes O(n). A heap balances these costs with O(log n) for both operations.