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.
use std::collections::BinaryHeap; let mut heap = BinaryHeap::new(); heap.push(3); heap.push(9); assert_eq!(heap.pop(), Some(9));
Try it
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.
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
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:
pushO(log n) (O(1) on average for random data),popO(log n),peekO(1),BinaryHeap::from(vec)O(n),into_sorted_vecO(n log n). - Iteration order is arbitrary.
iter(),into_iter()and{:?}show the internal layout. Useinto_sorted_vec()orpopfor sorted data. - Min-heap: use
Reverse(x). For tuples with anf64cost, wrap the cost in a type that implementsOrd(or store integer costs). - Custom order: implement
OrdandPartialOrdconsistently withEq, as in the second example. Inconsistent implementations break the heap's guarantees. peek_mutlets you change the top in place; the heap is repaired when thePeekMutguard 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.