Lesson 45 of 94
VecDeque & BinaryHeap
Two more collections complete the toolbox:
VecDeque<T>: a double-ended queue with O(1) push and pop at both ends, backed by a growable ring buffer. It's the right type for FIFO queues. (Vecis only fast at the back.)BinaryHeap<T>: a priority queue that always gives you the largest element first. It is a max-heap by default.
| Operation | Rust |
|---|---|
| Add at the back | VecDeque::push_back(x) |
| Add at the front | push_front(x) |
| Remove from the front | pop_front() returns Option |
| Remove from the back | pop_back() |
| Add to a priority queue | BinaryHeap::push(x) |
| Remove the top item | pop() (largest first) |
| Look at the top item | peek() |
| Max-heap | the default BinaryHeap |
| Min-heap | BinaryHeap<Reverse<T>> |
Part 1: VecDeque
1. A FIFO queue
use std::collections::VecDeque;
fn main() {
let mut queue: VecDeque<&str> = VecDeque::new();
queue.push_back("order-1");
queue.push_back("order-2");
queue.push_back("order-3");
while let Some(order) = queue.pop_front() {
println!("processing {order}, {} waiting", queue.len());
}
}processing order-1, 2 waiting
processing order-2, 1 waiting
processing order-3, 0 waitingVec::remove(0) would shift every remaining element on each call (O(n)). pop_front is O(1).
2. Both ends
use std::collections::VecDeque;
fn main() {
let mut d = VecDeque::from([2, 3]);
d.push_front(1);
d.push_back(4);
println!("{:?} front={:?} back={:?}", d, d.front(), d.back());
println!("{:?} {:?} {:?}", d.pop_front(), d.pop_back(), d);
}[1, 2, 3, 4] front=Some(1) back=Some(4)
Some(1) Some(4) [2, 3]3. Indexing and iterating
A VecDeque can be indexed and iterated in order, from front to back, like a Vec.
use std::collections::VecDeque;
fn main() {
let mut recent: VecDeque<&str> = VecDeque::from(["b", "c"]);
recent.push_front("a");
println!("{} {:?}", recent[0], recent.get(5));
let joined: Vec<&str> = recent.iter().copied().collect();
println!("{:?}", joined);
for page in recent.iter_mut() {
*page = "visited";
}
println!("{:?}", recent);
}a None
["a", "b", "c"]
["visited", "visited", "visited"]4. A bounded ring buffer: the last N items
Push new items at the back and drop the oldest from the front when full.
use std::collections::VecDeque;
struct Recent<T> {
items: VecDeque<T>,
cap: usize,
}
impl<T> Recent<T> {
fn push(&mut self, item: T) {
if self.items.len() == self.cap {
self.items.pop_front();
}
self.items.push_back(item);
}
}
fn main() {
let mut searches = Recent { items: VecDeque::with_capacity(3), cap: 3 };
for q in ["rust", "tokio", "serde", "axum", "sqlx"] {
searches.push(q);
println!("{:?}", searches.items);
}
}["rust"]
["rust", "tokio"]
["rust", "tokio", "serde"]
["tokio", "serde", "axum"]
["serde", "axum", "sqlx"]5. Moving average over the last N readings
use std::collections::VecDeque;
struct MovingAverage {
window: VecDeque<f64>,
size: usize,
sum: f64,
}
impl MovingAverage {
fn add(&mut self, value: f64) -> f64 {
self.window.push_back(value);
self.sum += value;
if self.window.len() > self.size {
self.sum -= self.window.pop_front().unwrap();
}
self.sum / self.window.len() as f64
}
}
fn main() {
let mut avg = MovingAverage { window: VecDeque::new(), size: 3, sum: 0.0 };
for v in [10.0, 20.0, 30.0, 40.0, 100.0] {
println!("add {v:>5} -> average {:.2}", avg.add(v));
}
}add 10 -> average 10.00
add 20 -> average 15.00
add 30 -> average 20.00
add 40 -> average 30.00
add 100 -> average 56.67Keeping a running sum makes each update O(1) instead of re-summing the window.
6. Rotating
use std::collections::VecDeque;
fn main() {
let mut players: VecDeque<&str> = VecDeque::from(["ana", "ben", "cy", "dee"]);
for turn in 1..=5 {
println!("turn {turn}: {}", players[0]);
players.rotate_left(1);
}
}turn 1: ana
turn 2: ben
turn 3: cy
turn 4: dee
turn 5: ana7. Draining, extending, and retaining
use std::collections::VecDeque;
fn main() {
let mut jobs: VecDeque<u32> = (1..=8).collect();
jobs.retain(|j| j % 4 != 0); // cancel jobs 4 and 8
let first_batch: Vec<u32> = jobs.drain(..3).collect();
jobs.extend([100, 101]);
println!("batch {:?}, remaining {:?}", first_batch, jobs);
}batch [1, 2, 3], remaining [5, 6, 7, 100, 101]8. Getting a contiguous slice
Because a VecDeque is a ring buffer, its elements may wrap around the end of its storage. as_slices returns the two parts; make_contiguous rearranges them into one slice, for example to sort.
use std::collections::VecDeque;
fn main() {
let mut d: VecDeque<i32> = VecDeque::with_capacity(4);
d.push_back(3);
d.push_back(4);
d.push_front(2);
d.push_front(1);
let (front, back) = d.as_slices();
println!("{} elements in the two parts", front.len() + back.len());
d.make_contiguous().sort_by(|a, b| b.cmp(a));
println!("{:?}", d);
}4 elements in the two parts
[4, 3, 2, 1]How the elements are split between the two slices depends on where the buffer wrapped, which is an implementation detail, so the example only prints the total. Code should never rely on the split.
9. Realistic example: breadth-first search on a grid
BFS explores the nearest cells first by using a FIFO queue. It finds the shortest path length in a maze.
use std::collections::VecDeque;
fn shortest_path(maze: &[&str]) -> Option<usize> {
let grid: Vec<Vec<char>> = maze.iter().map(|r| r.chars().collect()).collect();
let (rows, cols) = (grid.len(), grid[0].len());
let find = |ch: char| (0..rows).flat_map(|r| (0..cols).map(move |c| (r, c))).find(|&(r, c)| grid[r][c] == ch);
let start = find('S')?;
let goal = find('G')?;
let mut dist = vec![vec![usize::MAX; cols]; rows];
let mut queue = VecDeque::from([start]);
dist[start.0][start.1] = 0;
while let Some((r, c)) = queue.pop_front() {
if (r, c) == goal {
return Some(dist[r][c]);
}
let neighbors = [(r.wrapping_sub(1), c), (r + 1, c), (r, c.wrapping_sub(1)), (r, c + 1)];
for (nr, nc) in neighbors {
if nr < rows && nc < cols && grid[nr][nc] != '#' && dist[nr][nc] == usize::MAX {
dist[nr][nc] = dist[r][c] + 1;
queue.push_back((nr, nc));
}
}
}
None
}
fn main() {
let maze = ["S..#....", ".#.#.##.", ".#...#..", ".####.#.", "......#G"];
println!("{:?}", shortest_path(&maze));
println!("{:?}", shortest_path(&["S#G"]));
}Some(15)
Nonewrapping_sub(1) on 0 gives usize::MAX, which the bounds check nr < rows then rejects, a compact way to skip negative coordinates.
10. Realistic example: sliding window maximum
For each window of k consecutive values, find the maximum in O(n) total. The deque holds indexes of candidates in decreasing order of value.
use std::collections::VecDeque;
fn window_max(values: &[i32], k: usize) -> Vec<i32> {
let mut candidates: VecDeque<usize> = VecDeque::new();
let mut result = Vec::new();
for i in 0..values.len() {
while candidates.front().is_some_and(|&j| j + k <= i) {
candidates.pop_front(); // left the window
}
while candidates.back().is_some_and(|&j| values[j] <= values[i]) {
candidates.pop_back(); // can never be the max again
}
candidates.push_back(i);
if i + 1 >= k {
result.push(values[candidates[0]]);
}
}
result
}
fn main() {
let cpu_load = [12, 45, 30, 80, 20, 15, 60, 55, 10];
println!("{:?}", window_max(&cpu_load, 3));
}[45, 80, 80, 80, 60, 60, 60]11. Realistic example: undo and redo
Two stacks: actions to undo, and undone actions to redo. A VecDeque is used for the undo history so the oldest entries can be dropped from the front when the history is full.
use std::collections::VecDeque;
struct Editor {
text: String,
undo: VecDeque<String>,
redo: Vec<String>,
max_history: usize,
}
impl Editor {
fn type_text(&mut self, s: &str) {
if self.undo.len() == self.max_history {
self.undo.pop_front();
}
self.undo.push_back(self.text.clone());
self.redo.clear();
self.text.push_str(s);
}
fn undo(&mut self) {
if let Some(prev) = self.undo.pop_back() {
self.redo.push(std::mem::replace(&mut self.text, prev));
}
}
fn redo(&mut self) {
if let Some(next) = self.redo.pop() {
self.undo.push_back(std::mem::replace(&mut self.text, next));
}
}
}
fn main() {
let mut e = Editor { text: String::new(), undo: VecDeque::new(), redo: Vec::new(), max_history: 2 };
e.type_text("Hello");
e.type_text(", world");
e.type_text("!");
println!("{:?}", e.text);
e.undo();
e.undo();
e.undo(); // history only holds 2 steps
println!("{:?}", e.text);
e.redo();
println!("{:?}", e.text);
}"Hello, world!"
"Hello"
"Hello, world"Part 2: BinaryHeap
12. A max-heap by default
pop always returns the largest element.
use std::collections::BinaryHeap;
fn main() {
let mut heap = BinaryHeap::new();
for n in [3, 9, 1, 7, 5] {
heap.push(n);
}
println!("peek {:?}, len {}", heap.peek(), heap.len());
while let Some(n) = heap.pop() {
print!("{n} ");
}
println!();
}peek Some(9), len 5
9 7 5 3 113. A min-heap with Reverse
Wrap values in std::cmp::Reverse to flip the ordering, so the smallest comes out first.
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn main() {
let mut heap = BinaryHeap::new();
for n in [3, 9, 1, 7, 5] {
heap.push(Reverse(n));
}
while let Some(Reverse(n)) = heap.pop() {
print!("{n} ");
}
println!();
}1 3 5 7 914. Building a heap from a collection
BinaryHeap::from(vec) builds a heap in O(n). into_sorted_vec returns the elements in ascending order.
use std::collections::BinaryHeap;
fn main() {
let heap = BinaryHeap::from(vec![40, 10, 30, 20]);
println!("max {:?}", heap.peek());
println!("{:?}", heap.into_sorted_vec());
let words: BinaryHeap<&str> = ["pear", "apple", "zucchini"].into_iter().collect();
println!("{:?}", words.peek());
}max Some(40)
[10, 20, 30, 40]
Some("zucchini")15. Tuples as priorities
Tuples compare element by element, so (priority, item) pops the highest priority first, breaking ties by the item.
use std::collections::BinaryHeap;
fn main() {
let mut tickets = BinaryHeap::new();
tickets.push((2, "reset password"));
tickets.push((5, "site is down"));
tickets.push((3, "invoice wrong"));
tickets.push((5, "data breach"));
while let Some((priority, title)) = tickets.pop() {
println!("P{priority}: {title}");
}
}P5: site is down
P5: data breach
P3: invoice wrong
P2: reset password16. A custom priority with Ord
Implement Ord to define exactly what "largest" means. Here: higher priority first, and for equal priority, the earlier submission first (FIFO), using a sequence number.
use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(Debug, PartialEq, Eq)]
struct Job {
priority: u8,
seq: u64,
name: &'static str,
}
impl Ord for Job {
fn cmp(&self, other: &Self) -> Ordering {
self.priority.cmp(&other.priority).then_with(|| other.seq.cmp(&self.seq))
}
}
impl PartialOrd for Job {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn main() {
let mut queue = BinaryHeap::new();
let mut seq = 0;
for (priority, name) in [(1, "send newsletter"), (3, "charge card"), (1, "resize image"), (3, "refund"), (2, "email receipt")] {
seq += 1;
queue.push(Job { priority, seq, name });
}
while let Some(job) = queue.pop() {
println!("p{} #{} {}", job.priority, job.seq, job.name);
}
}p3 #2 charge card
p3 #4 refund
p2 #5 email receipt
p1 #1 send newsletter
p1 #3 resize image17. Floats need a total order
f64 isn't Ord, so it can't go into a BinaryHeap directly.
use std::collections::BinaryHeap;
fn main() {
let mut heap = BinaryHeap::new();
heap.push(2.5_f64);
}error[E0277]: the trait bound `f64: Ord` is not satisfied
--> src/main.rs:5:10
|
5 | heap.push(2.5_f64);
| ^^^^ the trait `Ord` is not implemented for `f64`
|
= help: the following other types implement trait `Ord`:
i128
i16
i32
i64
i8
isize
u128
u16
and 4 others
note: required by a bound in `BinaryHeap::<T, A>::push`
--> /rustc/<version>/library/alloc/src/collections/binary_heap/mod.rs:686:4A small wrapper that orders with total_cmp fixes it (alternatively, store integers such as cents or milliseconds).
use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(Debug, PartialEq)]
struct Score(f64);
impl Eq for Score {}
impl PartialOrd for Score {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Score {
fn cmp(&self, other: &Self) -> Ordering {
self.0.total_cmp(&other.0)
}
}
fn main() {
let heap: BinaryHeap<Score> = [0.72, 0.95, 0.31, 0.88].into_iter().map(Score).collect();
println!("{:?}", heap.into_sorted_vec().into_iter().rev().map(|s| s.0).collect::<Vec<_>>());
}[0.95, 0.88, 0.72, 0.31]18. peek_mut: change the top element in place
peek_mut gives mutable access to the largest element; the heap re-sorts itself when the guard is dropped.
use std::collections::BinaryHeap;
fn main() {
let mut budgets = BinaryHeap::from(vec![300, 800, 500]);
if let Some(mut top) = budgets.peek_mut() {
*top -= 450; // spend from the largest budget
}
println!("{:?}", budgets.into_sorted_vec());
}[300, 350, 500]19. Realistic example: top K with a bounded heap
To find the K largest values in a huge stream, keep a min-heap of size K. Each new value only replaces the smallest of the current top K. Memory stays O(K).
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn top_k(values: impl IntoIterator<Item = u32>, k: usize) -> Vec<u32> {
let mut heap: BinaryHeap<Reverse<u32>> = BinaryHeap::with_capacity(k + 1);
for v in values {
heap.push(Reverse(v));
if heap.len() > k {
heap.pop(); // drop the smallest
}
}
let mut result: Vec<u32> = heap.into_iter().map(|Reverse(v)| v).collect();
result.sort_unstable_by(|a, b| b.cmp(a));
result
}
fn main() {
let response_sizes = [512, 4_096, 128, 65_536, 2_048, 32_768, 1_024, 8_192];
println!("{:?}", top_k(response_sizes, 3));
println!("{:?}", top_k((1..=1_000_000_u64).map(|n| ((n * 7919) % 1_000_003) as u32), 5));
}[65536, 32768, 8192]
[1000002, 1000001, 1000000, 999999, 999998]20. Realistic example: merging K sorted lists
Each heap entry is (next value, which list, position). Popping the smallest and pushing that list's next value merges everything in O(n log k).
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn merge_sorted(lists: &[Vec<u32>]) -> Vec<u32> {
let mut heap = BinaryHeap::new();
for (i, list) in lists.iter().enumerate() {
if let Some(&first) = list.first() {
heap.push(Reverse((first, i, 0)));
}
}
let mut out = Vec::new();
while let Some(Reverse((value, list, pos))) = heap.pop() {
out.push(value);
if let Some(&next) = lists[list].get(pos + 1) {
heap.push(Reverse((next, list, pos + 1)));
}
}
out
}
fn main() {
let shards = vec![vec![1, 7, 12], vec![3, 4, 20, 21], vec![], vec![2, 15]];
println!("{:?}", merge_sorted(&shards));
}[1, 2, 3, 4, 7, 12, 15, 20, 21]This is how databases merge sorted runs from disk, and how log aggregators interleave timestamped logs from many servers.
21. Realistic example: Dijkstra's shortest paths
The classic priority-queue algorithm: always expand the closest unvisited node.
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
fn dijkstra<'a>(graph: &HashMap<&'a str, Vec<(&'a str, u32)>>, start: &'a str) -> HashMap<&'a str, u32> {
let mut dist: HashMap<&str, u32> = HashMap::from([(start, 0)]);
let mut heap = BinaryHeap::from([Reverse((0, start))]);
while let Some(Reverse((d, node))) = heap.pop() {
if d > dist[node] {
continue; // a stale entry: we already found a shorter path
}
for &(next, weight) in graph.get(node).map(|v| v.as_slice()).unwrap_or(&[]) {
let candidate = d + weight;
if dist.get(next).is_none_or(|¤t| candidate < current) {
dist.insert(next, candidate);
heap.push(Reverse((candidate, next)));
}
}
}
dist
}
fn main() {
let roads: HashMap<&str, Vec<(&str, u32)>> = HashMap::from([
("home", vec![("cafe", 4), ("park", 2)]),
("park", vec![("cafe", 1), ("office", 7)]),
("cafe", vec![("office", 3)]),
("office", vec![]),
]);
let dist = dijkstra(&roads, "home");
let mut rows: Vec<(&&str, &u32)> = dist.iter().collect();
rows.sort_by_key(|&(_, d)| *d);
for (place, d) in rows {
println!("{place:<7} {d} min");
}
}home 0 min
park 2 min
cafe 3 min
office 6 min22. Realistic example: a discrete event simulation
Events are processed in time order. Handling one event can schedule new ones in the future.
use std::cmp::Reverse;
use std::collections::BinaryHeap;
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Event {
Arrive(u32),
Depart(u32),
}
fn main() {
let mut events: BinaryHeap<Reverse<(u32, Event)>> = BinaryHeap::new();
for (t, customer) in [(0, 1), (2, 2), (3, 3)] {
events.push(Reverse((t, Event::Arrive(customer))));
}
let service_time = 4;
let mut server_free_at = 0;
while let Some(Reverse((time, event))) = events.pop() {
match event {
Event::Arrive(c) => {
let start = time.max(server_free_at);
server_free_at = start + service_time;
println!("t={time:>2} customer {c} arrives, served at {start}");
events.push(Reverse((server_free_at, Event::Depart(c))));
}
Event::Depart(c) => println!("t={time:>2} customer {c} leaves"),
}
}
}t= 0 customer 1 arrives, served at 0
t= 2 customer 2 arrives, served at 4
t= 3 customer 3 arrives, served at 8
t= 4 customer 1 leaves
t= 8 customer 2 leaves
t=12 customer 3 leaves23. Realistic example: tracking the running median
Keep the smaller half of the values in a max-heap and the larger half in a min-heap. The median is at the top of one or both.
use std::cmp::Reverse;
use std::collections::BinaryHeap;
#[derive(Default)]
struct RunningMedian {
low: BinaryHeap<i64>, // max-heap of the smaller half
high: BinaryHeap<Reverse<i64>>, // min-heap of the larger half
}
impl RunningMedian {
fn add(&mut self, x: i64) {
if self.low.peek().is_none_or(|&top| x <= top) {
self.low.push(x);
} else {
self.high.push(Reverse(x));
}
if self.low.len() > self.high.len() + 1 {
self.high.push(Reverse(self.low.pop().unwrap()));
} else if self.high.len() > self.low.len() {
self.low.push(self.high.pop().unwrap().0);
}
}
fn median(&self) -> f64 {
match (self.low.peek(), self.high.peek()) {
(Some(&l), Some(&Reverse(h))) if self.low.len() == self.high.len() => (l + h) as f64 / 2.0,
(Some(&l), _) => l as f64,
_ => 0.0,
}
}
}
fn main() {
let mut m = RunningMedian::default();
for latency in [120, 80, 300, 95, 110, 2_000] {
m.add(latency);
println!("after {latency:>4}: median {:.1}", m.median());
}
}after 120: median 120.0
after 80: median 100.0
after 300: median 120.0
after 95: median 107.5
after 110: median 110.0
after 2000: median 115.024. Realistic example: scheduling tasks on the least-loaded worker
A min-heap keyed by current load always hands the next task to the least busy worker.
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn main() {
let tasks = [("resize", 5), ("encode", 9), ("thumb", 2), ("upload", 4), ("scan", 7), ("notify", 1)];
let mut workers: BinaryHeap<Reverse<(u32, usize)>> = (0..3).map(|id| Reverse((0, id))).collect();
let mut assignment = vec![Vec::new(); 3];
for (name, cost) in tasks {
let Reverse((load, id)) = workers.pop().unwrap();
assignment[id].push(name);
workers.push(Reverse((load + cost, id)));
}
for (id, names) in assignment.iter().enumerate() {
println!("worker {id}: {:?}", names);
}
let makespan = workers.into_iter().map(|Reverse((load, _))| load).max().unwrap();
println!("finished after {makespan} units");
}worker 0: ["resize", "scan"]
worker 1: ["encode"]
worker 2: ["thumb", "upload", "notify"]
finished after 12 units25. Realistic example: rate-limited retries ordered by next attempt time
Failed deliveries wait in a min-heap keyed by the time they may be retried.
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn main() {
let mut retry_queue: BinaryHeap<Reverse<(u64, u32, &str)>> = BinaryHeap::new(); // (retry_at, attempt, webhook)
retry_queue.push(Reverse((0, 1, "https://a.example/hook")));
retry_queue.push(Reverse((0, 1, "https://b.example/hook")));
let succeeds_on = |url: &str, attempt: u32| url.contains("a.") || attempt >= 3;
while let Some(Reverse((at, attempt, url))) = retry_queue.pop() {
if succeeds_on(url, attempt) {
println!("t={at:>4} delivered to {url} on attempt {attempt}");
} else {
let next = at + 100 * 2u64.pow(attempt);
println!("t={at:>4} failed {url}, retry at t={next}");
retry_queue.push(Reverse((next, attempt + 1, url)));
}
}
}t= 0 delivered to https://a.example/hook on attempt 1
t= 0 failed https://b.example/hook, retry at t=200
t= 200 failed https://b.example/hook, retry at t=600
t= 600 delivered to https://b.example/hook on attempt 326. Choosing a collection
| You need | Use |
|---|---|
| A list, fast at the end | Vec<T> |
| A queue, fast at both ends | VecDeque<T> |
| The largest (or smallest) item repeatedly | BinaryHeap<T> (with Reverse for smallest) |
| Lookup by key, any order | HashMap<K, V> |
| Lookup by key, sorted, ranges | BTreeMap<K, V> |
| Unique values | HashSet<T> / BTreeSet<T> |
| A linked list | Almost never; Vec or VecDeque is faster. LinkedList exists for the rare splice-heavy case |
use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet, VecDeque};
fn main() {
let words = ["b", "a", "c", "a"];
let v: Vec<&str> = words.to_vec();
let q: VecDeque<&str> = words.into_iter().collect();
let h: BinaryHeap<&str> = words.into_iter().collect();
let s: HashSet<&str> = words.into_iter().collect();
let m: HashMap<&str, usize> = words.iter().enumerate().map(|(i, w)| (*w, i)).collect();
let t: BTreeMap<&str, usize> = words.iter().enumerate().map(|(i, w)| (*w, i)).collect();
println!("Vec {:?}", v);
println!("VecDeque front {:?}", q.front());
println!("BinaryHeap max {:?}", h.peek());
println!("HashSet {} unique", s.len());
println!("HashMap a -> {:?}", m.get("a"));
println!("BTreeMap {:?}", t);
}Vec ["b", "a", "c", "a"]
VecDeque front Some("b")
BinaryHeap max Some("c")
HashSet 3 unique
HashMap a -> Some(3)
BTreeMap {"a": 3, "b": 0, "c": 2}Summary
VecDeque<T>is a ring-buffer queue with O(1)push_front,push_back,pop_front, andpop_back. Use it for FIFO queues, BFS, sliding windows, and bounded histories.BinaryHeap<T>is a max-heap:popreturns the largest element. Wrap values inReversefor a min-heap.- Priorities come from
Ord: use tuples,Reverse, or a hand-writtenOrd(with a sequence number for FIFO ties). Floats need atotal_cmpwrapper. - Heaps power top-K, k-way merges, Dijkstra, event simulations, median tracking, and schedulers.
This completes the Collections section. Next: Modules & Visibility, the start of Modules, Crates & Testing, where your code leaves the single file.