When order of arrival doesn't matter
You're building a task scheduler. Tasks arrive with different urgency levels. A low-priority background cleanup shouldn't block a user request that needs immediate attention. You need a data structure that always hands you the most important item next, no matter the order things arrived. That's a priority queue. In Rust, std::collections::BinaryHeap gives you exactly that.
Grab BinaryHeap when the order of arrival doesn't matter, but the order of importance does.
The heap property and max-heap default
A binary heap is a tree-like structure stored in a flat array. The key rule is the heap property: every parent node must be greater than or equal to its children. This guarantees the largest element always sits at the root. You can access the top element in constant time, and inserting or removing elements takes logarithmic time.
Think of a tournament bracket. Players are paired up, winners advance, and the structure ensures the strongest competitor always reaches the final. BinaryHeap maintains this invariant automatically. You push items in, and the heap rearranges itself so the "largest" item bubbles to the top.
The default behavior is a max-heap. The element that compares as "largest" wins. If you store integers, the biggest number comes out first. If you store strings, the one that sorts last alphabetically comes out first. The heap relies on the Ord trait to determine order. Your type must implement Ord to define what "larger" means.
Remember: max-heap is the default. If you want the smallest item first, you have to ask for it explicitly.
Minimal example
Here's the basic usage. Create a heap, push values, and pop them out. The heap handles the ordering.
use std::collections::BinaryHeap;
fn main() {
// Create a heap. It starts empty and allocates on demand.
let mut heap = BinaryHeap::new();
// Push items. The heap reorders internally after each push.
heap.push(3);
heap.push(1);
heap.push(4);
// Peek at the top without removing it.
// This is O(1) and returns a reference.
if let Some(top) = heap.peek() {
println!("Top element is: {}", top);
}
// Pop returns the largest element first.
// The heap reorders itself after each pop to restore the invariant.
while let Some(val) = heap.pop() {
println!("Processing: {}", val);
}
}
The output shows 4, then 3, then 1. The heap extracted the maximum each time.
How push and pop maintain order
When you call push, the heap adds the new element to the end of the underlying vector. It then "bubbles up" the element, swapping it with its parent as long as the element is larger than the parent. This continues until the heap property is restored. The cost is proportional to the height of the tree, which is logarithmic relative to the number of elements.
pop removes the root element. It takes the last element in the vector, moves it to the root, and then "sifts down" by swapping it with the larger of its children. This repeats until the element lands in a spot where it's larger than both children. Again, logarithmic time.
peek just returns a reference to the first element in the vector. No movement, no swaps. Constant time.
The backing storage is a Vec. There are no pointers between nodes. The heap uses index arithmetic to find parents and children. For a node at index i, the left child is at 2*i + 1 and the right child is at 2*i + 2. This layout is cache-friendly and avoids pointer indirection.
Don't assume iter gives sorted output. Pop if you need order.
Realistic example: Tasks and priorities
Real code rarely stores plain integers. You usually have structs with fields. And you often want a min-heap where a lower priority number means higher urgency. Priority 1 is urgent. Priority 5 is low. BinaryHeap doesn't have a flag to flip the order. You teach it how to compare by implementing Ord.
use std::collections::BinaryHeap;
use std::cmp::Reverse;
/// Represents a task with an ID and a priority level.
/// Lower priority numbers indicate higher urgency.
#[derive(Debug, Eq, PartialEq)]
struct Task {
id: u32,
priority: u32,
}
// Implement Ord to sort tasks by priority.
// We reverse the comparison so smaller priority numbers come first.
impl Ord for Task {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
// Reverse the ordering: other.cmp(&self) makes smaller values "larger".
other.priority.cmp(&self.priority)
}
}
impl PartialOrd for Task {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
fn main() {
let mut tasks = BinaryHeap::new();
// Push tasks with varying priorities.
tasks.push(Task { id: 1, priority: 5 });
tasks.push(Task { id: 2, priority: 1 });
tasks.push(Task { id: 3, priority: 3 });
// Pop returns the task with the lowest priority number first.
while let Some(task) = tasks.pop() {
println!("Running task {} with priority {}", task.id, task.priority);
}
}
The output processes task 2 first (priority 1), then task 3 (priority 3), then task 1 (priority 5). The custom Ord implementation flipped the heap into a min-heap on the priority field.
Convention: Reverse for min-heaps
Writing a custom Ord implementation just to reverse the order is boilerplate-heavy. The community convention is to use std::cmp::Reverse. It's a zero-cost wrapper that implements Ord by flipping the comparison.
For simple types like integers, wrap the value in Reverse instead of writing a struct.
use std::collections::BinaryHeap;
use std::cmp::Reverse;
fn main() {
// Create a min-heap of integers using Reverse.
let mut min_heap = BinaryHeap::new();
// Wrap values in Reverse to invert the ordering.
min_heap.push(Reverse(3));
min_heap.push(Reverse(1));
min_heap.push(Reverse(4));
// Pop yields the smallest original value first.
while let Some(Reverse(val)) = min_heap.pop() {
println!("Value: {}", val);
}
}
This outputs 1, then 3, then 4. The Reverse wrapper signals intent clearly. Anyone reading the code sees Reverse and knows immediately this is a min-heap.
Wrap values in Reverse for min-heaps. It saves boilerplate and signals intent to anyone reading the code.
Pitfalls and compiler errors
The biggest trap is the Ord requirement. BinaryHeap demands total ordering. If you try to push a type that only implements PartialOrd, the compiler rejects you with E0277 (trait bound not satisfied). You can't have a priority queue if you can't definitively say which item is bigger. Floating point numbers with NaN break total ordering, which is why f64 doesn't implement Ord by default.
Another common confusion involves iteration. iter() yields elements in arbitrary order. It walks the internal array, which satisfies the heap property but is not sorted. If you need sorted output, you must pop elements one by one.
use std::collections::BinaryHeap;
fn main() {
let mut heap = BinaryHeap::from([3, 1, 4]);
// iter() does NOT return sorted elements.
// The order depends on the internal heap layout.
for val in heap.iter() {
println!("Unsorted: {}", val);
}
}
Calling into_vec has the same behavior. It returns the underlying vector without sorting. The result satisfies the heap invariant, but it's not ascending or descending. If you need a sorted vector, pop everything into a new vector.
You also can't mutate items inside the heap. BinaryHeap provides no get_mut or iter_mut. Changing a value in place could violate the heap property. The compiler enforces this by omitting mutable access methods. If you need to modify an item, pop it, change it, and push it back.
If you try to use a type without Ord, fix the trait bound. Don't try to mutate items in place. Pop, modify, push back. The heap structure relies on stability.
Limitations: Updating and removing
BinaryHeap is optimized for pushing and popping. It doesn't support efficient updates or arbitrary removals. There's no "decrease-key" operation to update the priority of an existing element. If you need to change a task's priority, you have to pop elements until you find it, modify it, and push it back. In the worst case, that's linear time.
Removing an arbitrary element is also linear. You'd have to find the element, swap it with the last element, remove the last, and then sift the replacement up or down. The API doesn't expose this because it's rarely the right pattern. If your workload requires frequent updates or removals, BinaryHeap is the wrong tool. Consider a BTreeMap keyed by priority, or a custom structure that maintains handles to elements.
Pick the tool that matches your access pattern. If you only care about the top, the heap is your friend. If you need updates, look elsewhere.
Decision matrix
Use BinaryHeap when you need to repeatedly extract the maximum or minimum element from a dynamic collection. Use BinaryHeap when insertion and extraction both need logarithmic performance, like in Dijkstra's algorithm or a task scheduler. Use a sorted Vec when the data is static or you need random access by index; sorting a vector is faster for bulk operations, but inserting in the middle is linear. Use BTreeMap when you need to look up elements by key or iterate in order; the map gives you key-based access that the heap cannot provide. Reach for BinaryHeap when the "next best" item is the only thing that matters, and the rest of the order is irrelevant.