Push and Pop Operations
Implementing insertion and extraction in heaps. Learn sift-up and sift-down operations for maintaining the heap property.
The two fundamental heap operations are push (insert) and pop (extract). Both maintain the heap property by "sifting" elements up or down the tree. Understanding these operations is key to implementing priority queues.
Sift Up (Bubble Up)
When inserting, we add the element at the end (to maintain completeness) and then "sift up" to restore the heap property.
Insert 85 into max-heap [90, 70, 80, 40, 50, 60]:
Step 1: Add at end
90
/ \
70 80
/ \ / \
40 50 60 85 <- Added here
Step 2: Compare 85 with parent 80
85 > 80, swap!
90
/ \
70 85
/ \ / \
40 50 60 80
Step 3: Compare 85 with parent 90
85 < 90, done!
Result: [90, 70, 85, 40, 50, 60, 80]
Implementation
struct MaxHeap {
heap: Vec<i32>,
}
impl MaxHeap {
fn new() -> Self {
MaxHeap { heap: Vec::new() }
}
fn push(&mut self, val: i32) {
self.heap.push(val);
self.sift_up(self.heap.len() - 1);
}
fn sift_up(&mut self, mut i: usize) {
while i > 0 {
let parent = (i - 1) / 2;
if self.heap[i] <= self.heap[parent] {
break;
}
// Swap with parent
self.heap.swap(i, parent);
i = parent;
}
}
}
For a min-heap, change <= to >=:
struct MinHeap {
heap: Vec<i32>,
}
impl MinHeap {
fn new() -> Self {
MinHeap { heap: Vec::new() }
}
fn push(&mut self, val: i32) {
self.heap.push(val);
self.sift_up(self.heap.len() - 1);
}
fn sift_up(&mut self, mut i: usize) {
while i > 0 {
let parent = (i - 1) / 2;
if self.heap[i] >= self.heap[parent] {
break;
}
self.heap.swap(i, parent);
i = parent;
}
}
}
Sift Down (Bubble Down)
When extracting the root, we:
- Replace root with the last element
- Remove the last position
- Sift down from the root to restore heap property
Extract from max-heap [90, 70, 85, 40, 50, 60, 80]:
Step 1: Save root (90), replace with last (80)
80
/ \
70 85
/ \ /
40 50 60
Step 2: Compare 80 with children (70, 85)
Largest child is 85, 80 < 85, swap!
85
/ \
70 80
/ \ /
40 50 60
Step 3: Compare 80 with children (60)
80 > 60, done!
Result: [85, 70, 80, 40, 50, 60], return 90
Implementation
impl MaxHeap {
// ... previous methods ...
fn pop(&mut self) -> Option<i32> {
if self.heap.is_empty() {
return None;
}
// Save the root value
let result = self.heap[0];
// Move last element to root
if let Some(last) = self.heap.pop() {
if !self.heap.is_empty() {
self.heap[0] = last;
self.sift_down(0);
}
}
Some(result)
}
fn sift_down(&mut self, mut i: usize) {
let n = self.heap.len();
loop {
let mut largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if left < n && self.heap[left] > self.heap[largest] {
largest = left;
}
if right < n && self.heap[right] > self.heap[largest] {
largest = right;
}
if largest == i {
break;
}
self.heap.swap(i, largest);
i = largest;
}
}
}
Why Swap with Last Element?
Removing from the middle of an array is O(n). By moving the last element to the root, we maintain the complete tree property and only need O(log n) sift operations to restore the heap property.
Complete Min-Heap Implementation
struct MinHeap {
heap: Vec<i32>,
}
impl MinHeap {
fn new() -> Self {
MinHeap { heap: Vec::new() }
}
fn push(&mut self, val: i32) {
self.heap.push(val);
self.sift_up(self.heap.len() - 1);
}
fn pop(&mut self) -> Option<i32> {
if self.heap.is_empty() {
return None;
}
let result = self.heap[0];
if let Some(last) = self.heap.pop() {
if !self.heap.is_empty() {
self.heap[0] = last;
self.sift_down(0);
}
}
Some(result)
}
fn peek(&self) -> Option<i32> {
self.heap.get(0).copied()
}
fn sift_up(&mut self, mut i: usize) {
while i > 0 {
let parent = (i - 1) / 2;
if self.heap[i] >= self.heap[parent] {
break;
}
self.heap.swap(i, parent);
i = parent;
}
}
fn sift_down(&mut self, mut i: usize) {
let n = self.heap.len();
loop {
let mut smallest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if left < n && self.heap[left] < self.heap[smallest] {
smallest = left;
}
if right < n && self.heap[right] < self.heap[smallest] {
smallest = right;
}
if smallest == i {
break;
}
self.heap.swap(i, smallest);
i = smallest;
}
}
fn len(&self) -> usize {
self.heap.len()
}
fn is_empty(&self) -> bool {
self.heap.is_empty()
}
}
// Usage
fn main() {
let mut heap = MinHeap::new();
for val in [5, 3, 8, 1, 2, 7] {
heap.push(val);
}
while !heap.is_empty() {
println!("{}", heap.pop().unwrap()); // 1, 2, 3, 5, 7, 8
}
}
Time Complexity
| Operation | Time | Description | |-----------|------|-------------| | push | O(log n) | Sift up at most height levels | | pop | O(log n) | Sift down at most height levels | | peek | O(1) | Access root directly |
The height of a heap with n elements is ⌊log₂(n)⌋, so both sift operations are O(log n).
Visualizing Sift Operations
Sift Up (after insert 95 into [90, 70, 80]):
90 90 95
/ \ insert / \ sift / \
70 80 ---> 70 80 up 90 80
\ /
95 70
Sift Down (after pop from [90, 70, 80, 40]):
90 40 80
/ \ replace / \ sift / \
70 80 root 70 80 down 70 40
/ / /
40 (empty) (empty)
Sift Down Direction
When sifting down in a max-heap, always swap with the LARGER child. In a min-heap, swap with the SMALLER child. This maintains the heap property efficiently.
Using Rust's BinaryHeap
Rust provides a built-in max-heap in the standard library:
use std::collections::BinaryHeap;
use std::cmp::Reverse;
// Create a max-heap
let mut max_heap = BinaryHeap::new();
max_heap.push(5);
max_heap.push(3);
max_heap.push(8);
max_heap.push(1);
println!("{}", max_heap.peek().unwrap()); // 8 (peek at max)
println!("{}", max_heap.pop().unwrap()); // 8
println!("{}", max_heap.pop().unwrap()); // 5
// For min-heap, use Reverse wrapper
let mut min_heap = BinaryHeap::new();
min_heap.push(Reverse(5));
min_heap.push(Reverse(3));
min_heap.push(Reverse(8));
min_heap.push(Reverse(1));
println!("{}", min_heap.pop().unwrap().0); // 1 (smallest)
println!("{}", min_heap.pop().unwrap().0); // 3
Heap with Custom Objects
Using tuples or custom comparisons:
use std::collections::BinaryHeap;
use std::cmp::Reverse;
// Priority queue with (priority, task)
// Use Reverse for min-heap behavior
let mut pq = BinaryHeap::new();
pq.push(Reverse((2, "task B")));
pq.push(Reverse((1, "task A")));
pq.push(Reverse((3, "task C")));
while let Some(Reverse((priority, task))) = pq.pop() {
println!("{} (priority {})", task, priority);
}
// Output:
// task A (priority 1)
// task B (priority 2)
// task C (priority 3)
Applications
Top K Elements
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn find_k_largest(nums: &[i32], k: usize) -> Vec<i32> {
// Find k largest elements using min-heap of size k
let mut heap = BinaryHeap::new();
for &num in nums {
heap.push(Reverse(num));
if heap.len() > k {
heap.pop();
}
}
let mut result: Vec<i32> = heap.into_iter().map(|Reverse(x)| x).collect();
result.sort_by(|a, b| b.cmp(a)); // Sort descending
result
}
fn main() {
let nums = vec![3, 1, 4, 1, 5, 9, 2, 6];
println!("{:?}", find_k_largest(&nums, 3)); // [9, 6, 5]
}
Merge K Sorted Lists
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn merge_k_sorted(lists: Vec<Vec<i32>>) -> Vec<i32> {
// Merge k sorted lists using min-heap
let mut result = Vec::new();
let mut heap = BinaryHeap::new();
// Initialize heap with first element of each list
for (i, list) in lists.iter().enumerate() {
if !list.is_empty() {
heap.push(Reverse((list[0], i, 0)));
}
}
while let Some(Reverse((val, list_idx, element_idx))) = heap.pop() {
result.push(val);
// Push next element from same list
if element_idx + 1 < lists[list_idx].len() {
let next_val = lists[list_idx][element_idx + 1];
heap.push(Reverse((next_val, list_idx, element_idx + 1)));
}
}
result
}
Key Takeaways
- Push: Add at end, sift up to restore heap property
- Pop: Replace root with last, sift down to restore heap property
- Both operations are O(log n)
- Sift up compares with parent; sift down compares with children
- For max-heap: swap when child > parent; for min-heap: swap when child < parent
- Rust's BinaryHeap provides efficient max-heap operations (use Reverse for min-heap)
Understanding sift up and sift down is fundamental for heaps. These operations form the basis of heap sort, priority queues, and many graph algorithms.