VecDeque and BinaryHeap

VecDeque as a double-ended queue and BinaryHeap as a max-heap, including Reverse for a min-heap and why iterating a heap is not a sorted walk.

主题页正文目前为英文。

VecDeque<T> and BinaryHeap<T> both live in std::collections. The collections page already covers BTreeMap and HashSet, and HashMap has its own page. This page is the double-ended queue and the heap: they are not a rewrite of those maps and sets.

BinaryHeap is a max-heap: peek and pop yield the greatest element under Ord. Wrap values in Reverse to get min-heap order. Iterating a BinaryHeap does not walk the elements in sorted order. Examples were compiled with rustc 1.90.0 and --edition=2024.

Examples were compiled with rustc 1.90.0 using --edition=2024 and run as a plain binary. See the Rust 1.90.0 documentation for the complete API.

Rust reference overview →

API index

APISummary
VecDeque::push_front, push_back, pop_front, pop_backGrow or shrink a double-ended queue at either end. Pops return Option and do not panic on an empty queue.
BinaryHeap::push, peek, pop, iter, and ReversePush and pop a max-heap, wrap values in Reverse for min-heap order, and treat heap iteration as unordered.

VecDeque as a double-ended queue

VecDeque is a growable ring buffer. push_front and pop_front work at the front; push_back and pop_back work at the back. An empty pop returns None rather than panicking. Indexing a VecDeque panics out of range, the same way a Vec does; get returns Option.

VecDeque::push_front, push_back, pop_front, pop_back

pub fn push_front(&mut self, value: T)
pub fn push_back(&mut self, value: T)
pub fn pop_front(&mut self) -> Option<T>
pub fn pop_back(&mut self) -> Option<T>

Grow or shrink a double-ended queue at either end. Pops return Option and do not panic on an empty queue.

ParameterDescription
valueThe element to insert at the front or back.

Returns: The push methods return (). The pop methods return Some(value) or None when the queue is empty.

  • From([2, 3]) starts with 2 at the front. After push_front(1) and push_back(4), pop_front yields 1 and pop_back yields 4, leaving [2, 3].
  • make_contiguous can be used when you need a single &mut [T] view. This page does not restate slice methods.
rust
use std::collections::VecDeque;

fn main() {
    let mut q = VecDeque::from([2, 3]);
    q.push_front(1);
    q.push_back(4);
    println!("front={:?} back={:?} mid={:?}", q.pop_front(), q.pop_back(), q);
}

Expected output

front=Some(1) back=Some(4) mid=[2, 3]

Related: BTreeMap and HashSet, Vec

Official documentation →

BinaryHeap is a max-heap

BinaryHeap<T: Ord> is a binary max-heap. peek and pop return the largest element, not the smallest, and not an insertion-order view. To get a min-heap, store Reverse(value) and unwrap it on pop. The cmp page documents Reverse itself.

iter() and into_iter() visit the heap in an arbitrary order. Official documentation does not promise that this order is sorted. The example collects the iterator, sorts a copy for display, and reports the length. Do not treat a printed iteration order as a contract.

BinaryHeap::push, peek, pop, iter, and Reverse

pub fn push(&mut self, item: T)
pub fn peek(&self) -> Option<&T>
pub fn pop(&mut self) -> Option<T>
pub fn iter(&self) -> Iter<'_, T>
pub struct Reverse<T>(pub T);

Push and pop a max-heap, wrap values in Reverse for min-heap order, and treat heap iteration as unordered.

ParameterDescription
itemA value that implements Ord. For a min-heap, item is typically Reverse(inner).

Returns: peek borrows the current maximum. pop takes it. Both return None on an empty heap.

  • Repeated pop on BinaryHeap::from([3, 1, 4, 2]) yields [4, 3, 2, 1]. The same values wrapped in Reverse pop as [1, 2, 3, 4].
  • iter_sorted in the output is a sorted copy of the collected iterator, made only so the printed line is deterministic. The iterator itself is not a sorted walk.
rust
use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut max_heap = BinaryHeap::from([3, 1, 4, 2]);
    println!("peek={:?}", max_heap.peek());
    let mut popped = Vec::new();
    while let Some(value) = max_heap.pop() {
        popped.push(value);
    }
    println!("max_pop={popped:?}");

    let mut min_heap = BinaryHeap::new();
    for value in [3, 1, 4, 2] {
        min_heap.push(Reverse(value));
    }
    let mut min_popped = Vec::new();
    while let Some(Reverse(value)) = min_heap.pop() {
        min_popped.push(value);
    }
    println!("min_pop={min_popped:?}");

    let heap = BinaryHeap::from([3, 1, 4]);
    let mut seen: Vec<_> = heap.iter().copied().collect();
    seen.sort();
    println!("iter_sorted={seen:?} len={}", heap.len());
}

Expected output

peek=Some(4)
max_pop=[4, 3, 2, 1]
min_pop=[1, 2, 3, 4]
iter_sorted=[1, 3, 4] len=3

Related: Reverse and Ordering, Official BinaryHeap

Official documentation →