Heaps & Priority Queues

A heap is a tree-based data structure that maintains the heap property: in a max-heap, every parent is greater than or equal to its children. Heaps are the foundation of priority queues, enabling O(log n) insert and O(1) peek at the maximum (or minimum).

Implementing heaps in Rust involves:

• Array representation: Mapping tree structure to array indices
• Generic ordering: Supporting both min-heaps and max-heaps
• Efficient updates: Bubble-up and bubble-down operations
• Integration: Working with Rust's Ord trait

use std::cmp::Ordering;

/// A binary max-heap implementation
#[derive(Debug)]
pub struct MaxHeap<T> {
    data: Vec<T>,
}

impl<T: Ord> MaxHeap<T> {
    pub fn new() -> Self {
        MaxHeap { data: Vec::new() }
    }

    pub fn with_capacity(capacity: usize) -> Self {
        MaxHeap { data: Vec::with_capacity(capacity) }
    }

    /// Build heap from existing data - O(n)
    pub fn from_vec(mut data: Vec<T>) -> Self {
        let len = data.len();
        let mut heap = MaxHeap { data };

        // Heapify from bottom up (more efficient than inserting one by one)
        for i in (0..len / 2).rev() {
            heap.sift_down(i);
        }

        heap
    }

    pub fn push(&mut self, value: T) {
        self.data.push(value);
        self.sift_up(self.data.len() - 1);
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.data.is_empty() {
            return None;
        }

        let len = self.data.len();
        self.data.swap(0, len - 1);
        let max = self.data.pop();

        if !self.data.is_empty() {
            self.sift_down(0);
        }

        max
    }

    pub fn peek(&self) -> Option<&T> {
        self.data.first()
    }

    pub fn len(&self) -> usize {
        self.data.len()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    fn sift_up(&mut self, mut index: usize) {
        while index > 0 {
            let parent = (index - 1) / 2;
            if self.data[index] > self.data[parent] {
                self.data.swap(index, parent);
                index = parent;
            } else {
                break;
            }
        }
    }

    fn sift_down(&mut self, mut index: usize) {
        let len = self.data.len();
        loop {
            let left = 2 * index + 1;
            let right = 2 * index + 2;
            let mut largest = index;

            if left < len && self.data[left] > self.data[largest] {
                largest = left;
            }
            if right < len && self.data[right] > self.data[largest] {
                largest = right;
            }

            if largest != index {
                self.data.swap(index, largest);
                index = largest;
            } else {
                break;
            }
        }
    }
}

impl<T: Ord> Default for MaxHeap<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// A min-heap using Reverse wrapper
#[derive(Debug)]
pub struct MinHeap<T> {
    heap: MaxHeap<Reverse<T>>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct Reverse<T>(T);

impl<T: Ord> Ord for Reverse<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        other.0.cmp(&self.0) // Reverse the comparison
    }
}

impl<T: Ord> PartialOrd for Reverse<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T: Ord> MinHeap<T> {
    pub fn new() -> Self {
        MinHeap { heap: MaxHeap::new() }
    }

    pub fn push(&mut self, value: T) {
        self.heap.push(Reverse(value));
    }

    pub fn pop(&mut self) -> Option<T> {
        self.heap.pop().map(|r| r.0)
    }

    pub fn peek(&self) -> Option<&T> {
        self.heap.peek().map(|r| &r.0)
    }

    pub fn len(&self) -> usize {
        self.heap.len()
    }

    pub fn is_empty(&self) -> bool {
        self.heap.is_empty()
    }
}

impl<T: Ord> Default for MinHeap<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// Priority queue with custom priority
pub struct PriorityQueue<T, P> {
    heap: MaxHeap<PriorityItem<T, P>>,
}

#[derive(Debug)]
struct PriorityItem<T, P> {
    item: T,
    priority: P,
}

impl<T, P: Ord> Ord for PriorityItem<T, P> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority.cmp(&other.priority)
    }
}

impl<T, P: Ord> PartialOrd for PriorityItem<T, P> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T, P: Ord> PartialEq for PriorityItem<T, P> {
    fn eq(&self, other: &Self) -> bool {
        self.priority == other.priority
    }
}

impl<T, P: Ord> Eq for PriorityItem<T, P> {}

impl<T, P: Ord> PriorityQueue<T, P> {
    pub fn new() -> Self {
        PriorityQueue { heap: MaxHeap::new() }
    }

    pub fn push(&mut self, item: T, priority: P) {
        self.heap.push(PriorityItem { item, priority });
    }

    pub fn pop(&mut self) -> Option<T> {
        self.heap.pop().map(|pi| pi.item)
    }

    pub fn peek(&self) -> Option<&T> {
        self.heap.peek().map(|pi| &pi.item)
    }

    pub fn is_empty(&self) -> bool {
        self.heap.is_empty()
    }
}

impl<T, P: Ord> Default for PriorityQueue<T, P> {
    fn default() -> Self {
        Self::new()
    }
}

/// K smallest elements using a max-heap
pub fn k_smallest<T: Ord + Clone>(items: &[T], k: usize) -> Vec<T> {
    if k == 0 || items.is_empty() {
        return Vec::new();
    }

    let k = k.min(items.len());
    let mut heap = MaxHeap::from_vec(items[..k].to_vec());

    for item in &items[k..] {
        if item < heap.peek().unwrap() {
            heap.pop();
            heap.push(item.clone());
        }
    }

    let mut result = Vec::with_capacity(k);
    while let Some(item) = heap.pop() {
        result.push(item);
    }
    result.reverse();
    result
}

fn main() {
    // Max-heap
    let mut max_heap = MaxHeap::new();
    for &n in &[3, 1, 4, 1, 5, 9, 2, 6] {
        max_heap.push(n);
    }

    println!("Max-heap extraction:");
    while let Some(n) = max_heap.pop() {
        print!("{} ", n); // 9 6 5 4 3 2 1 1
    }
    println!();

    // Min-heap
    let mut min_heap = MinHeap::new();
    for &n in &[3, 1, 4, 1, 5, 9, 2, 6] {
        min_heap.push(n);
    }

    println!("Min-heap extraction:");
    while let Some(n) = min_heap.pop() {
        print!("{} ", n); // 1 1 2 3 4 5 6 9
    }
    println!();

    // Priority queue
    let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
    pq.push("Low priority task", 1);
    pq.push("High priority task", 10);
    pq.push("Medium priority task", 5);

    println!("Priority queue:");
    while let Some(task) = pq.pop() {
        println!("  {}", task);
    }

    // K smallest
    let numbers = vec![7, 3, 9, 1, 5, 8, 2, 6, 4];
    let smallest_3 = k_smallest(&numbers, 3);
    println!("3 smallest: {:?}", smallest_3); // [1, 2, 3]
}

1. Array-based tree: Indices map parent/child relationships without pointers
2. sift_up/sift_down: Maintain heap property in O(log n)
3. from_vec in O(n): Bottom-up heapification is more efficient than n inserts
4. Reverse wrapper: Elegantly converts max-heap to min-heap

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    // Max-heap (default)
    let mut max_heap = BinaryHeap::from([3, 1, 4, 1, 5]);
    println!("Max: {:?}", max_heap.peek()); // Some(5)

    // Min-heap using Reverse
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    min_heap.push(Reverse(3));
    min_heap.push(Reverse(1));
    min_heap.push(Reverse(4));
    println!("Min: {:?}", min_heap.peek().map(|r| r.0)); // Some(1)

    // Drain in order
    while let Some(Reverse(n)) = min_heap.pop() {
        println!("{}", n);
    }
}

| Application | Heap Type | Example |

|-------------|-----------|---------|

| Job scheduling | Max-heap by priority | OS process scheduler |

| Dijkstra's algorithm | Min-heap by distance | Shortest path |

| Median finding | Max + min heap | Running median |

| K-way merge | Min-heap of iterators | External sorting |

| Event simulation | Min-heap by time | Discrete event simulation |

• Operating systems: Process scheduling
• Databases: Top-k queries
• Games: AI pathfinding (A*)
• Networking: Bandwidth allocation

1. Implement decrease_key for Dijkstra's algorithm
2. Create a d-ary heap (generalize to d children)
3. Implement merge of two heaps
4. Build a running median calculator using two heaps