Collection Adapters and Specialized Types

BinaryHeap vs. Priority Queue Implementations

While std::collections::BinaryHeap<T> is the standard priority queue for single-ended push, peek, and pop workloads, some algorithms (such as Dijkstra's shortest path with decrease_key, double-ended priority queues, or key-addressable cancellation) require comparing BinaryHeap against BTreeSet or a lazy-deletion BinaryHeap.

Comparing Priority Queue Approaches in Standard Rust

Capability BinaryHeap<T> BTreeSet<(Priority, Id)> Sorted Vec<T>
Inspect maximum (peek / last) $O(1)$ $O(\log n)$ $O(1)$
Inspect both min and max No ($O(1)$ for one end only) $O(\log n)$ (first & last) $O(1)$ (first & last)
Push new item $O(\log n)$ (amortized $O(1)$) $O(\log n)$ $O(n)$ (shift)
Pop highest priority $O(\log n)$ $O(\log n)$ (pop_last) $O(1)$ (pop from back)
Update / cancel arbitrary queued item (decrease_key / remove) Not directly supported (use lazy deletion) $O(\log n)$ (remove(&old) + insert(new)) $O(n)$
Duplicate items allowed? Yes Via unique tie-breaker (prio, id) Yes
Memory layout Single contiguous Vec<T> Multi-element B-Tree nodes Single contiguous Vec<T>

Pattern 1: Lazy Deletion in BinaryHeap (Dijkstra's Algorithm)

Standard BinaryHeap<T> does not provide a handle to decrease the key of an arbitrary interior element in place. In practice, pushing a new (Reverse(shorter_dist), node) entry into the BinaryHeap and ignoring stale entries when popped (if d > dist[u] { continue; }) is faster than maintaining an indexed heap handle array because BinaryHeap sits in a single contiguous Vec:

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

fn dijkstra(adj: &[Vec<(usize, u64)>], start: usize) -> Vec<u64> {
    let mut dist = vec![u64::MAX; adj.len()];
    let mut pq: BinaryHeap<Reverse<(u64, usize)>> = BinaryHeap::new();

    dist[start] = 0;
    pq.push(Reverse((0, start)));

    while let Some(Reverse((d, u))) = pq.pop() {
        // Lazy deletion check: skip stale heap entries whose distance was already improved!
        if d > dist[u] {
            continue;
        }

        for &(v, weight) in &adj[u] {
            let next_d = d + weight;
            if next_d < dist[v] {
                dist[v] = next_d;
                pq.push(Reverse((next_d, v)));
            }
        }
    }
    dist
}

fn main() {
    let graph = vec![
        vec![(1, 10), (2, 3)], // 0 -> 1 (10), 0 -> 2 (3)
        vec![(3, 2)],          // 1 -> 3 (2)
        vec![(1, 4), (3, 8)],  // 2 -> 1 (4),  2 -> 3 (8)
        vec![],
    ];

    println!("Shortest distances from 0: {:?}", dijkstra(&graph, 0));
}

Shortest distances from 0: [0, 7, 3, 9]

Pattern 2: Key-Addressable Priority Queue with BTreeSet + HashMap

When queued jobs can be canceled or reprioritized by job_id before execution (and cannot leave stale entries accumulating in memory), pair a HashMap<JobId, Priority> (to look up the current priority of a job) with a BTreeSet<(Priority, JobId)> (to pop the highest/lowest priority or remove (old_prio, job_id) in $O(\log n)$ time):

use std::collections::{BTreeSet, HashMap};

struct UpdatablePriorityQueue {
    by_id: HashMap<&'static str, u32>,
    ordered: BTreeSet<(u32, &'static str)>,
}

impl UpdatablePriorityQueue {
    fn new() -> Self {
        Self {
            by_id: HashMap::new(),
            ordered: BTreeSet::new(),
        }
    }

    fn upsert(&mut self, job_id: &'static str, new_priority: u32) {
        if let Some(old_priority) = self.by_id.insert(job_id, new_priority) {
            self.ordered.remove(&(old_priority, job_id));
        }
        self.ordered.insert((new_priority, job_id));
    }

    fn pop_highest(&mut self) -> Option<(&'static str, u32)> {
        let (prio, id) = self.ordered.pop_last()?;
        self.by_id.remove(id);
        Some((id, prio))
    }
}

fn main() {
    let mut pq = UpdatablePriorityQueue::new();
    pq.upsert("backup", 10);
    pq.upsert("compile", 50);
    pq.upsert("backup", 99); // Reprioritize "backup" from 10 -> 99 in O(log n)

    println!("1st popped: {:?}", pq.pop_highest());
    println!("2nd popped: {:?}", pq.pop_highest());
}

1st popped: Some(("backup", 99))
2nd popped: Some(("compile", 50))