BinaryHeap<T>

How Rust's BinaryHeap provides a priority queue backed by a binary heap, and how to use it for max-heap, min-heap, and custom ordering scenarios

What `BinaryHeap<T>` Is

BinaryHeap<T> is Rust's standard priority queue, built on a binary heap data structure. By default it acts as a max-heap: the largest element, according to T's Ord implementation, is always at the front and will be popped first. You can turn it into a min‑heap by wrapping values in std::cmp::Reverse or by implementing Ord to reverse the ordering.

A binary heap is a complete binary tree stored in a contiguous array — no pointers, no per‑node allocations. This layout makes it memory‑efficient and cache‑friendly. Inserting and removing the top element both run in O(log n) time, and peeking at the top is O(1).

It is a max-heap by default:

Unless you explicitly change the ordering, heap.pop() returns the largest value. If you call pop() and get a smaller number than you expected, you might be thinking of a min‑heap.

Why BinaryHeap Exists

Many programs need to repeatedly grab the most important item from a collection: the task with the highest priority, the smallest key in a graph traversal, the next event on a timeline. A vector can be sorted, but sorting on every insertion is expensive. BinaryHeap solves this by keeping the collection partially ordered — just enough order to guarantee that the top element is always available in constant time, while insertion and removal stay logarithmic.

Concretely, use BinaryHeap when you want:

O(1) access to the maximum (or minimum) element
O(log n) insertion and removal
No need for full sorted order at every moment

If you need the whole collection sorted once, Vec::sort is fine. If you need repeated sorted‑order extraction from a changing collection, a binary heap is the right tool.

How the Binary Heap Works Internally

A binary heap stores elements in a flat array that represents a complete binary tree. For any element at index i:

Its parent is at (i - 1) / 2
Its left child is at 2*i + 1
Its right child is at 2*i + 2

The heap invariant (max‑heap version) says that every parent must be greater than or equal to its children. The invariant does not sort the whole array — it only guarantees that the root (index 0) is the largest element.

When you push a new value, it is placed at the end of the array and then bubbled up (sifted up) by swapping it with its parent until the invariant holds again. When you pop the root, the last element is moved to the root and bubbled down (sifted down) by swapping with the larger of its two children until the invariant is restored.

This mechanism explains why iter() returns elements in an arbitrary order — the array is heap‑ordered, not sorted — and why modifying an element in place is dangerous: the heap does not automatically re‑order when a value changes.

Creating and Using a BinaryHeap

Constructing a Heap

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(5);

You can also create a heap from an array or vector. The From implementation builds the heap in O(n) time.

let heap = BinaryHeap::from([3, 1, 5]);

If you know roughly how many elements you will insert, BinaryHeap::with_capacity pre‑allocates memory, avoiding repeated reallocations.

let mut heap = BinaryHeap::with_capacity(100);
heap.push(4);

Core Operations

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::from([1, 5, 2]);
// Peek at the top without removing it.
assert_eq!(heap.peek(), Some(&5));
// Pop removes and returns the greatest element.
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);
// Length and emptiness.
assert!(heap.is_empty());

The code above pushes three integers and then pops them in descending order. The first pop returns 5 (the largest), followed by 2, then 1. This is the fundamental behaviour: a max‑heap always hands back the largest remaining element.

Iteration, Conversion, and Cleanup

Iterating over a BinaryHeap with for x in &heap yields elements in arbitrary heap order — do not rely on it being sorted.

let heap = BinaryHeap::from([1, 5, 2]);
for x in &heap {
    println!("{x}"); // order not guaranteed
}

To get the elements in sorted ascending order while consuming the heap, use into_sorted_vec.

let heap = BinaryHeap::from([3, 1, 2]);
let sorted = heap.into_sorted_vec(); // [1, 2, 3]

into_vec returns the underlying array in heap order (arbitrary from the user's perspective), which can be useful if you want to repurpose the allocation.

drain() removes all elements and returns an iterator over them in arbitrary order, leaving the heap empty. clear() simply drops all elements. append(&mut other) moves all elements from another heap into this one, leaving other empty.

Iteration is not sorted:

A common beginner mistake is to assume for x in &heap will print elements in sorted order. It won't. If you need sorted output, use into_sorted_vec or repeatedly pop while the heap is not empty.

Turning a Max‑Heap into a Min‑Heap

BinaryHeap is inherently a max‑heap, but you can reverse the ordering so that pop() returns the smallest element. Rust provides two straightforward ways.

Wrap each value in std::cmp::Reverse. The Reverse wrapper flips the comparison direction, so a max‑heap of Reverse(i32) behaves like a min‑heap of i32.

use std::collections::BinaryHeap;
use std::cmp::Reverse;
let mut heap = BinaryHeap::new();
heap.push(Reverse(3));
heap.push(Reverse(1));
heap.push(Reverse(5));
assert_eq!(heap.pop(), Some(Reverse(1))); // smallest
assert_eq!(heap.pop(), Some(Reverse(3)));
assert_eq!(heap.pop(), Some(Reverse(5)));

Both approaches are valid:

If all you need is a simple reversed numeric order, Reverse is concise and zero‑cost. When you have a custom type and need more control — for instance, comparing multiple fields — implement Ord directly.

Working with Custom Types

Anything stored in a BinaryHeap must implement Ord. For your own structs, derive or implement Ord (and PartialOrd, Eq, PartialEq) so the heap can compare instances.

Here, a Task struct is prioritized by priority (higher number = more urgent), and ties are broken by id.

use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(Debug, Eq, PartialEq)]
struct Task {
    priority: u32,
    id: u32,
}
impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority.cmp(&other.priority)
            .then_with(|| other.id.cmp(&self.id)) // tie-breaker
    }
}
impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
let mut heap = BinaryHeap::new();
heap.push(Task { priority: 2, id: 100 });
heap.push(Task { priority: 5, id: 10  });
heap.push(Task { priority: 5, id: 20  });
// Highest priority first; equal priority → lower id wins (due to reversed tie)
assert_eq!(heap.pop(), Some(Task { priority: 5, id: 10 }));
assert_eq!(heap.pop(), Some(Task { priority: 5, id: 20 }));
assert_eq!(heap.pop(), Some(Task { priority: 2, id: 100 }));

The then_with call flips the comparison for id by using other.id.cmp(&self.id). This makes the tie‑breaker select the task with the smaller id among those with equal priority. Without this subtlety, two tasks with identical priority would be considered equal (and the heap would drop one of them because Ord consistency demands a total order — Rust does not allow undefined behaviour here, but the heap’s behaviour would be unpredictable). Always ensure your Ord implementation defines a total order.

Ord must define a total order:

If two elements compare as equal (Ordering::Equal), BinaryHeap treats them as logically identical for ordering purposes. The heap may keep both, but relative order between equal items is unspecified and may change. Make sure your Ord produces a consistent total order — use then_with to break ties.

PeekMut – Mutable Access to the Top Element

peek_mut returns an Option<PeekMut<T>>, a guard that gives a mutable reference to the greatest element. You can modify the value in place, and when the guard is dropped the heap reorders itself to maintain the invariant.

use std::collections::BinaryHeap;
let mut heap = BinaryHeap::from([1, 3, 5]);
if let Some(mut top) = heap.peek_mut() {
    *top = 0; // reduce the greatest value
}
// After the guard is dropped, the heap re‑sifts the modified element.
assert_eq!(heap.peek(), Some(&3)); // 3 is now the largest

Modifying the value through PeekMut triggers a sift‑down (or sift‑up) operation, so the cost is O(log n) if the value actually changes order. If you read but don't modify, it's O(1).

Do not hold two PeekMut guards at once:

peek_mut takes &mut self and returns a guard that keeps the heap borrowed. You cannot call peek_mut again or any other method that requires &mut self until the guard is dropped. If you leak the guard (e.g., via std::mem::forget), the heap will be in a valid but incomplete state — some elements may be leaked, but no undefined behaviour occurs.

Performance Characteristics

The table below summarizes the time complexity of the main operations. n is the number of elements in the heap.

Operation	Time complexity
`peek` / `peek_mut` (no change)	O(1)
`push`	Expected O(1), worst‑case O(log n) amortized
`pop`	O(log n)
`into_sorted_vec`	O(n log n)
`from` (building from an array)	O(n)
`peek_mut` with modification	O(log n)

The "expected O(1)" for push is worth understanding. It assumes elements arrive in random order. When elements are pushed in ascending sorted order (into a max‑heap), the new item often has to bubble all the way to the root, degrading to O(log n) amortized per push. In practice, for unpredictable input, push is very fast.

Memory: the heap uses a single Vec under the hood. Capacity grows like a vector — doubling when full, so reallocation cost is amortized O(1) per element.

Common Mistakes and Misconceptions

Assuming iteration is sorted

Iterating with .iter() or a for loop returns elements in heap order, which is not sorted. Use .into_sorted_vec() or repeated .pop() if you need sorted output.

Forgetting that BinaryHeap is a max‑heap by default

Calling pop() on a heap of [1, 5, 2] returns 5, not 1. To get a min‑heap, wrap items in Reverse or implement a reversed Ord.

Modifying an element while it's in the heap

If an element's ordering changes after insertion (through interior mutability, global state, or unsafe code), the heap invariant may break. This is a logic error. The heap will not automatically reorder, and subsequent operations may return incorrect results or panic.

Do not mutate heap elements outside of peek_mut:

Once an item is inside the heap, its Ord comparison with other items must remain stable. The only safe way to change a heap element is through peek_mut, which re‑sifts it afterward.

Using a partial order

Ord must define a total order. If cmp returns Ordering::Equal for two distinct elements, the heap may behave unpredictably (e.g., drop one of them, or order them inconsistently). Always break ties using a secondary key.

Holding multiple peek_mut guards

The borrow checker prevents this at compile time, but it's still worth knowing that peek_mut returns a guard that holds an exclusive reference. Don't attempt to call other &mut self methods until the guard is dropped.

Real‑World Use Cases

Task scheduling: A thread pool or async runtime can keep ready tasks in a BinaryHeap keyed by priority, popping the most urgent task in O(log n).

Dijkstra's algorithm: The shortest‑path frontier is a min‑heap of candidate nodes, allowing the algorithm to always expand the closest unvisited node. The classic Rust example in the standard library documentation demonstrates exactly this pattern.

Event simulation: Store events with timestamps. Pop the earliest event (min‑heap), process it, and push any new events it generates.

Top‑K elements: To find the k largest elements in a stream, maintain a min‑heap of size k. For each new element, if it's larger than the heap's current minimum, replace the minimum. The heap ends up containing the top k.

Summary

BinaryHeap<T> gives you a priority queue that prioritizes insertion and retrieval of the maximum (or minimum, with a flipped order) over maintaining full sorted order. Its array‑backed, complete‑tree implementation delivers O(log n) operations and constant‑time top access, making it a practical choice for any workload that revolves around repeatedly picking the most important item.

The key takeaways:

A BinaryHeap is a max‑heap by default; use Reverse or a custom Ord for a min‑heap.
Never modify an element while it's inside the heap except through peek_mut.
Iteration is arbitrary; sorted output requires into_sorted_vec or sequential pop.
Ord must be total — break ties or risk inconsistent behavior.

When you need sorted iteration across an entire collection without further insertions, sorting a vector is simpler. But when the collection changes over time and you repeatedly need the top element, BinaryHeap is the right tool.

PreviousLinkedlistt

Next Hashmapk V And Btree...