Standard Collections

BinaryHeap<T>

BinaryHeap<T> (std::collections::BinaryHeap<T>) is a priority queue implemented as a binary max-heap stored inside a contiguous Vec<T>, keeping the largest element (according to T: Ord) at the root for $O(1)$ inspection and $O(\log n)$ removal.

Heap Structure and Array Representation

A binary max-heap is a complete binary tree where every parent node is greater than or equal to its children (parent >= left and parent >= right), stored flat inside a Vec<T> where node i has children at indices 2*i + 1 and 2*i + 2:

Logical Max-Heap Tree:           Contiguous Backing Array (`Vec<i32>`):
          90                     +----+----+----+----+----+----+
        /    \                   | 90 | 75 | 80 | 30 | 60 | 20 |
      75      80                 +----+----+----+----+----+----+
     /  \    /                    [0]  [1]  [2]  [3]  [4]  [5]
   30   60  20

Core BinaryHeap<T> Operations

Method Time Complexity Behavior
BinaryHeap::from(vec) $O(n)$ (Floyd's heapify) Builds a max-heap from an unsorted Vec<T> or [T; N] in linear time
heap.peek() -> Option<&T> $O(1)$ Returns a shared reference to the maximum element without removing it
heap.push(item) $O(\log n)$ (amortized $O(1)$) Appends item and sifts it up to restore the heap invariant
heap.pop() -> Option<T> $O(\log n)$ Removes and returns the maximum element
heap.into_sorted_vec() -> Vec<T> $O(n \log n)$ Consumes the heap and returns a Vec<T> sorted in ascending order 
use std::collections::BinaryHeap;

fn main() {
    // O(n) bulk construction from an array:
    let mut heap = BinaryHeap::from([30, 90, 20, 75, 60, 80]);

    println!("Max element (.peek()): {:?}", heap.peek());
    println!("Popped 1st max:        {:?}", heap.pop());
    println!("Popped 2nd max:        {:?}", heap.pop());

    // Important: `.iter()` visits elements in arbitrary heap-array order, NOT sorted order!
    let sorted = heap.into_sorted_vec();
    println!("Remaining sorted ascending: {sorted:?}");
}

Max element (.peek()): Some(&90)
Popped 1st max:        Some(90)
Popped 2nd max:        Some(80)
Remaining sorted ascending: [20, 30, 60, 75]

Creating a Min-Heap with std::cmp::Reverse<T>

Because BinaryHeap<T> is a max-heap by default, wrap elements in std::cmp::Reverse<T> (which inverts the Ord implementation of T) to turn BinaryHeap<Reverse<T>> into a min-heap that always pops the smallest element first:

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut min_heap = BinaryHeap::new();
    min_heap.push(Reverse(50));
    min_heap.push(Reverse(10));
    min_heap.push(Reverse(30));

    while let Some(Reverse(smallest)) = min_heap.pop() {
        print!("{smallest} ");
    }
    println!();
}

10 30 50