Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust BinaryHeap<T> type

Reference for Rust BinaryHeap<T>: a max-heap priority queue with push, pop, peek, into_sorted_vec, Reverse for min-heaps and custom ordering.

BinaryHeap<T> is a priority queue backed by a binary max-heap stored in a Vec<T>. push inserts a value in O(log n), pop removes and returns the greatest value in O(log n), and peek reads it in O(1). The element type must implement Ord.

The heap only guarantees that the largest element is at the top. Iterating a heap does not give sorted order; call into_sorted_vec() or pop repeatedly for that. For a min-heap, wrap values in std::cmp::Reverse. The standard use cases are Dijkstra's algorithm, scheduling, merging sorted streams and "top k" selection.

Rust
use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(9);
assert_eq!(heap.pop(), Some(9));

Try it

Rust Max-heap and min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rust Custom priority and top k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Syntax

Rust
pub struct BinaryHeap<T, A = Global> { /* private */ }

impl<T: Ord> BinaryHeap<T> {
    pub const fn new() -> BinaryHeap<T>;
    pub fn with_capacity(capacity: usize) -> BinaryHeap<T>;
    pub fn push(&mut self, item: T);
    pub fn pop(&mut self) -> Option<T>;
    pub fn peek(&self) -> Option<&T>;
    pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>>;
    pub fn into_sorted_vec(self) -> Vec<T>;
    pub fn into_vec(self) -> Vec<T>;
    pub fn append(&mut self, other: &mut BinaryHeap<T>);
    pub fn drain(&mut self) -> Drain<'_, T>;
}
Name Description
item The value to add; it takes its place by Ord.
other Heap to merge in with append; left empty.

Returns: pop and peek return None on an empty heap. into_sorted_vec returns the elements in ascending order (the reverse of pop order).

Errors and panics: none. If a value's ordering changes while it is inside the heap (interior mutability), the heap order becomes unspecified, though still memory-safe.

Usage notes

  • Complexity: push O(log n) (O(1) on average for random data), pop O(log n), peek O(1), BinaryHeap::from(vec) O(n), into_sorted_vec O(n log n).
  • Iteration order is arbitrary. iter(), into_iter() and {:?} show the internal layout. Use into_sorted_vec() or pop for sorted data.
  • Min-heap: use Reverse(x). For tuples with an f64 cost, wrap the cost in a type that implements Ord (or store integer costs).
  • Custom order: implement Ord and PartialOrd consistently with Eq, as in the second example. Inconsistent implementations break the heap's guarantees.
  • peek_mut lets you change the top in place; the heap is repaired when the PeekMut guard is dropped. PeekMut::pop(guard) removes it.
  • Not stable: equal elements pop in unspecified order. Add a sequence number to the key if you need FIFO among equals.
  • No decrease-key. Dijkstra implementations push a new entry and skip stale ones when popped.
  • Build from data fast: BinaryHeap::from(vec) heapifies in linear time, faster than pushing one by one.