The priority queue problem
You are building a background job processor. New tasks arrive at random intervals. Some are routine maintenance. Others are user-facing requests that need immediate attention. You need a data structure that always hands you the most urgent task next, without scanning the entire list every time. That is exactly what BinaryHeap does.
Rust's standard library provides std::collections::BinaryHeap as a priority queue. It guarantees that the largest element is always accessible in constant time. The structure does not keep the entire collection sorted. It only guarantees the top element is the maximum. Iterating over a BinaryHeap yields elements in an arbitrary order. If you need full sorting, you are looking at a different tool.
Think of it like a hospital triage system. Patients arrive and get tagged with a severity score. The nurse does not sort the entire waiting room from scratch when someone new walks in. She places the new patient in the right spot relative to the existing ones. When it is time to treat someone, she always picks the highest score first. The structure stays organized with minimal effort.
Rust's implementation is a max-heap. The "largest" element sits at the top. If you need a min-heap, you wrap your values in std::cmp::Reverse. The heap optimizes for the edges, not the middle. You get fast insertion and fast extraction of the extreme value. You lose random access and sorted iteration.
How the heap stays organized
A binary heap is a complete binary tree stored in a flat Vec. The tree property is maintained through index arithmetic. For any element at index i, its left child lives at 2*i + 1 and its right child at 2*i + 2. The parent of any node is at (i - 1) / 2. This layout eliminates pointer indirection and keeps memory access predictable. The CPU cache loves it.
When you insert an element, the heap appends it to the end of the vector. It then compares the new item with its parent. If the new item is larger, they swap. This sift-up process continues until the heap property holds. The cost is O(log n) because the height of a binary tree grows logarithmically with the number of elements.
Removal works in reverse. The heap takes the root, drops the last element into the root slot, and sifts down by swapping with the larger child until order is restored. Also O(log n). Peeking at the top is O(1) because the maximum is always at index zero.
The tradeoff is explicit. You sacrifice middle-range access and sorted traversal to gain logarithmic insertion and extraction. The structure is built for queues, not databases.
Minimal working example
use std::collections::BinaryHeap;
fn main() {
let mut heap = BinaryHeap::new();
// Push adds to the end, then sifts up to restore the heap property.
heap.push(42);
heap.push(17);
heap.push(89);
heap.push(5);
// Peek looks at the top without removing it. O(1) operation.
if let Some(&top) = heap.peek() {
println!("Highest priority: {}", top);
}
// Pop removes the top, replaces it with the last element, then sifts down.
while let Some(val) = heap.pop() {
println!("Processing: {}", val);
}
}
The code above demonstrates the core lifecycle. new allocates an empty vector. push maintains the invariant. peek gives you a reference to the maximum without mutation. pop consumes the maximum and returns it. The loop drains the structure safely.
Notice the &top in the if let pattern. peek returns Option<&T>. Destructuring with &top extracts the value directly, avoiding an extra dereference later. Small pattern choices like this keep the borrow checker happy and the code readable.
Walking through the operations
Insertion and extraction are the only operations that touch the internal ordering. Everything else is a wrapper around the underlying vector. len and is_empty delegate directly to Vec. clear drops all elements and resets the capacity. drain consumes the heap and yields elements in heap order, not sorted order.
If you need a sorted vector at the end of your pipeline, call into_sorted_vec(). It runs a heap sort in O(n log n) and consumes the heap. The method is useful when you have collected priorities throughout a computation and only need the final ranking at the very end. Calling it mid-process defeats the purpose of using a heap in the first place.
The heap does not support stable ordering. If two elements compare as equal, their relative order after insertion and extraction is undefined. The sift-up and sift-down algorithms only care about the comparison result, not insertion history. If stability matters, you must encode it into your comparison logic.
Real-world priority handling
Real code rarely deals with bare integers. You will usually wrap a struct. To use a struct in a BinaryHeap, it must implement Ord and PartialOrd. The compiler will reject you with E0277 (trait bound not satisfied) if you skip this.
use std::collections::BinaryHeap;
use std::cmp::Ordering;
#[derive(Debug, PartialEq, Eq)]
struct Job {
id: u32,
priority: i32,
name: String,
}
// BinaryHeap requires Ord to determine which element belongs at the top.
impl Ord for Job {
fn cmp(&self, other: &Self) -> Ordering {
// Compare priority first. Higher number means higher priority.
self.priority.cmp(&other.priority)
// Break ties by ID to guarantee a total ordering.
.then_with(|| other.id.cmp(&self.id))
}
}
// PartialOrd is required by the trait hierarchy, even though Ord is total.
impl PartialOrd for Job {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn main() {
let mut queue = BinaryHeap::new();
queue.push(Job { id: 1, priority: 5, name: "Backup".to_string() });
queue.push(Job { id: 2, priority: 10, name: "Deploy".to_string() });
queue.push(Job { id: 3, priority: 5, name: "Cleanup".to_string() });
// Process until empty
while let Some(job) = queue.pop() {
println!("Running: {} (Priority: {})", job.name, job.priority);
}
}
The tie-breaker in cmp is mandatory. If two jobs share the same priority, cmp must still return a definitive ordering. Without a tie-breaker, you risk violating the total ordering requirement. Heap algorithms assume transitivity and antisymmetry. Breaking those assumptions leads to infinite loops or silent data corruption during sift operations. The community standard is to chain comparisons with .then_with() or .then() until every field is accounted for.
Prefer #[derive(PartialEq, Eq)] over manual implementations unless you have a specific reason. The derive macros generate correct, optimized code. Manual equality checks often introduce subtle bugs when the heap reorders elements during rebalancing.
The trait contract and common traps
The Ord trait inherits from PartialOrd, which inherits from PartialEq, which inherits from Eq. You must implement the full chain. The compiler enforces this strictly. Forgetting PartialOrd when you implement Ord triggers E0277. Implement PartialOrd by delegating to Ord::cmp wrapped in Some. This keeps the implementations in sync and prevents divergence.
Max-heap confusion is the most frequent beginner mistake. Rust's heap puts the largest value on top. If you want the smallest value first, wrapping in Reverse is the standard pattern. BinaryHeap::new() followed by heap.push(Reverse(42)) gives you a min-heap. The wrapper flips the comparison logic without requiring a separate data structure. It is zero-cost and idiomatic.
Iteration surprise catches many developers off guard. for item in heap does not yield sorted items. It yields them in heap order. The internal array is arranged to satisfy parent-child constraints, not left-to-right ordering. If you print the heap directly, the output will look random. Trust the pop order, not the iteration order.
Mutable access is impossible by design. You cannot mutate elements inside the heap. The heap property depends on the values staying consistent. If you need to update priorities, pop the element, modify it, and push it back. The community calls this the "extract-modify-reinsert" pattern. It preserves the invariant without requiring interior mutability or unsafe code.
Treat the Ord implementation as a contract. If your comparison logic changes mid-execution, the heap breaks. Never store mutable priority fields inside a heap element. Keep the priority immutable, or rebuild the heap when priorities shift.
When to reach for BinaryHeap
Use BinaryHeap when you need frequent insertions and extractions of the maximum or minimum element, and you do not need to iterate in sorted order. Use a sorted Vec when your dataset is small, changes infrequently, and you need full range queries or binary search. Use BTreeMap or BTreeSet when you need ordered iteration, range queries, or fast lookups by key alongside priority ordering. Use VecDeque when you need a simple FIFO queue with O(1) pushes and pops from both ends, and priority does not matter.
The heap is a specialist tool. It shines in event loops, Dijkstra pathfinding, Huffman coding, and top-K element selection. It struggles when you need to update arbitrary elements or scan the middle of the dataset. Pick the structure that matches your access pattern, not the one that sounds impressive.