Collection Adapters and Specialized Types

Max-Heap Operations

BinaryHeap<T> supports $O(1)$ maximum inspection (.peek()), $O(\log n)$ in-place root modification via PeekMut (.peek_mut()), $O(\log n)$ insertion (.push()), and $O(\log n)$ maximum extraction (.pop()).

Core Max-Heap Methods

Method Signature Time Complexity Behavior
heap.push(val) fn push(&mut self, item: T) $O(\log n)$ (amortized $O(1)$) Appends item to the end of the backing Vec and sifts up until parent >= item
heap.pop() fn pop(&mut self) -> Option<T> $O(\log n)$ Swaps root v[0] with last element, pops the max, and sifts down the new root
heap.peek() fn peek(&self) -> Option<&T> $O(1)$ Returns a shared reference &v[0] to the maximum element
heap.peek_mut() fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> $O(1)$ (sifts down on drop if mutated) Returns a RAII guard allowing in-place mutation or PeekMut::pop of the root 
1. Sift-Up on `heap.push(95)`:
   Appends 95 at leaf [5] ──> swaps with parent 60 at [2] ──> stops below root 100 at [0]

2. Sift-Down on `heap.pop()`:
   Removes root 100 at [0], moves last leaf into [0], swaps down with larger child until heap property holds

Modifying the Root In-Place with peek_mut() (PeekMut)

When you need to modify the maximum element at the top of the heap (for example, reducing a task's remaining quota or replacing the root with a new item) without calling pop() followed by push() (which would sift down and then sift up), use heap.peek_mut():

  • PeekMut<'_, T> implements DerefMut<Target = T>.
  • If you mutate the root through PeekMut, its Drop implementation automatically sifts the modified root down to restore the heap invariant once when PeekMut goes out of scope!
  • Calling PeekMut::pop(guard) removes and returns the root element directly.
use std::collections::BinaryHeap;
use std::collections::binary_heap::PeekMut;

fn main() {
    let mut scores = BinaryHeap::from([50, 90, 75]);

    // 1. Halve the maximum score (90 -> 45) in place; `PeekMut::drop` sifts 45 down automatically:
    if let Some(mut top) = scores.peek_mut() {
        *top /= 2;
    }
    println!("New max after halving 90 -> 45: {:?}", scores.peek());

    // 2. Conditionally pop the root using `PeekMut::pop`:
    if let Some(top) = scores.peek_mut() {
        if *top >= 70 {
            let popped = PeekMut::pop(top);
            println!("Conditionally popped: {popped}");
        }
    }
    println!("Max remaining: {:?}", scores.peek());
}

New max after halving 90 -> 45: Some(&75)
Conditionally popped: 75
Max remaining: Some(&50)