VecDeque, BinaryHeap & LinkedList

VecDeque is a double-ended queue. BinaryHeap is a priority queue (max-heap). LinkedList is rarely the right choice in Rust.

Recipe

use std::collections::{BinaryHeap, VecDeque};
 
fn main() {
    let mut q = VecDeque::from([1, 2]);
    q.push_front(0);
 
    let mut heap = BinaryHeap::from([1, 3, 2]);
    assert_eq!(heap.pop(), Some(3));
}

When to reach for this: BFS queues, schedulers, top-K problems - avoid LinkedList unless you have measured need.

Working Example

use std::collections::BinaryHeap;
 
#[derive(Eq, PartialEq)]
struct Task { priority: u8, name: &'static str }
impl Ord for Task {
    fn cmp(&self, o: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&o.priority)
    }
}
impl PartialOrd for Task { fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(o)) } }
 
fn main() {
    let mut h = BinaryHeap::new();
    h.push(Task { priority: 1, name: "low" });
    h.push(Task { priority: 10, name: "high" });
    println!("{}", h.pop().unwrap().name);
}

What this demonstrates:

• Custom Ord for heap ordering
• Max-heap pops highest priority first
• VecDeque for FIFO with front/back ops

Deep Dive

LinkedList allocates per node - poor cache locality. Prefer Vec or VecDeque unless intrusive list required.

BinaryHeap::peek reads max without pop. VecDeque::make_contiguous for slice access.

Gotchas

• LinkedList by default - Slower than VecDeque. Fix: Benchmark before using.
• Min-heap - Reverse Ord or use std::cmp::Reverse.
• Heap with equal keys - Order not stable. Fix: Tie-breaker field in Ord.
• VecDeque ring buffer growth - Still amortized efficient.
• Pop from empty heap - Returns None.

Alternatives

FAQs

Related

• Collections Basics
• Vec & Slices
• Iterator Adapters
• High Performance Data

Stack versions: This page was written for Rust 1.97.0 (edition 2024), Tokio 1.x, Axum 0.8, serde 1.0, sqlx 0.8, clap 4, and Polars 0.46+.