🎓 A1Learner
🔍
0 of 142 lessons completed

Rust Priority Queues

A priority queue is a line that always serves the most urgent item next. Rust's priority queue is called BinaryHeap.

Push jobs in any order

Each item is a (priority, job) tuple. The biggest priority rules, so push in whatever order is convenient.

use std::collections::BinaryHeap;

let mut queue = BinaryHeap::new();
queue.push((3, "water the plants"));
queue.push((9, "fix the leak"));
queue.push((5, "answer email"));

Peek without taking

peek looks at the top item without removing it. None when the heap is empty.

println!("{:?}", queue.peek());

pop always takes the biggest

The most urgent job comes out first — then the next — until the heap is empty and pop returns None.

println!("{:?}", queue.pop());
println!("{:?}", queue.pop());
println!("{:?}", queue.pop());
println!("{:?}", queue.pop());

Smallest first instead (Reverse)

There is no separate min-heap type — wrap each item in Reverse and the smallest floats to the top.

use std::cmp::Reverse;

let mut lows: BinaryHeap<Reverse<(u8, &str)>> = BinaryHeap::new();
lows.push(Reverse((2, "second")));
lows.push(Reverse((1, "first")));
println!("{:?}", lows.pop());

Example

use std::collections::BinaryHeap;

fn main() {
    let mut triage: BinaryHeap<(u8, &str)> = BinaryHeap::new();
    triage.push((2, "sprained ankle"));
    triage.push((10, "chest pain"));
    triage.push((5, "broken finger"));
    triage.push((1, "mild cold"));
    println!("treating {} patients:", triage.len());
    while !triage.is_empty() {
        let (urgency, case) = triage.pop().unwrap();
        println!("[{urgency}] {case}");
    }
    println!("queue empty: {}", triage.is_empty());
}

Key points

  • A priority queue ignores arrival order: the biggest item leaves first, every time.
  • BinaryHeap lives in std::collections, next to HashMap and Vec — it is part of std, not a crate.
  • It is a max-heap: the largest value is always on top, however you pushed the items in.
  • With tuples, the first item decides.
  • Ties fall to the second item, then the third.
  • The comparison walks left to right.
  • push and pop stay fast even for huge queues.
  • Each one touches only a short chain of swaps, never the whole heap.

The four cases are pushed in a random order. But pop always returns the highest urgency first: 10, 5, 2, 1. pop hands back an Option, because the heap can be empty. The loop runs while the heap is not empty, and unwrap takes each case out. The Option lesson, later in this course, unpacks Option in full. is_empty() confirms the heap is empty at the end. The tuple's number is the whole sorting rule. The text just rides along.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

What does pop return when a BinaryHeap is empty?