Rust and Data Structures

Binary Heaps

A binary heap, implemented in the standard library as std::collections::BinaryHeap<T>, is a priority queue backed by a flat contiguous Vec<T> that keeps the highest-priority element at the root (index 0) in $O(1)$ peek time and supports insertion and extraction in $O(\log n)$ time.

Max-Heap Tree Logical View:               Contiguous `Vec<T>` Physical Storage:
            [ 90 ] (idx 0)                Index:  0    1    2    3    4    5
           /      \                              +----+----+----+----+----+----+
     [ 70 ] (1)  [ 80 ] (2)                      | 90 | 70 | 80 | 30 | 50 | 40 |
      /    \      /                              +----+----+----+----+----+----+
   [30](3) [50](4) [40](5)                Parent(i) = (i - 1) / 2
                                          Left(i)   = 2*i + 1,  Right(i) = 2*i + 2

Complexity of BinaryHeap<T> Operations

Operation Method Time Complexity Notes
Inspect Maximum heap.peek() $O(1)$ Returns Option<&T> for the largest element (vec[0]).
Mutate Root in Place heap.peek_mut() $O(\log n)$ on drop Returns a PeekMut guard that sifts the modified root down when dropped (or removes it via PeekMut::pop).
Insert Element heap.push(item) $O(\log n)$ ($O(1)$ average) Appends to the end of the Vec and sifts up.
Extract Maximum heap.pop() $O(\log n)$ Swaps root with last element, pops it, and sifts new root down.
Build Heap from Vec<T> BinaryHeap::from(vec) $O(n)$ (Floyd's algorithm!) Much faster than $n$ calls to push ($O(n \log n)$)!

Turning BinaryHeap (Max-Heap) into a Min-Heap with std::cmp::Reverse

By default, BinaryHeap<T> is a max-heap (pop() returns the largest T according to Ord).

To create a min-heap (needed for Dijkstra's shortest-path algorithm, A* search, timer wheels, or finding the Top $K$ largest items in a stream) without implementing a custom Ord wrapper, wrap each element in std::cmp::Reverse<T>, which inverts the comparison order (a.cmp(b).reverse()):

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

/// Finds the `k` largest numbers in an arbitrarily large stream in O(n log k) time
/// and O(k) memory by maintaining a Min-Heap of size `k` using `Reverse`!
pub fn top_k_largest(stream: &[u64], k: usize) -> Vec<u64> {
    if k == 0 {
        return Vec::new();
    }

    // Min-heap of at most `k` elements: `heap.peek()` is the SMALLEST of the top `k` so far!
    let mut min_heap: BinaryHeap<Reverse<u64>> = BinaryHeap::with_capacity(k);

    for &val in stream {
        if min_heap.len() < k {
            min_heap.push(Reverse(val));
        } else if let Some(mut smallest_top) = min_heap.peek_mut() {
            if val > smallest_top.0 {
                // Replace the smallest of the top-k in-place (1 sift-down instead of pop + push!)
                *smallest_top = Reverse(val);
            }
        }
    }

    // Extract in ascending order from the min-heap
    let mut out: Vec<u64> = min_heap.into_iter().map(|Reverse(x)| x).collect();
    out.sort_unstable();
    out
}

fn main() {
    // 1. O(n) bulk heap construction from Vec:
    let mut max_heap = BinaryHeap::from(vec![20, 80, 50, 10, 90]);
    assert_eq!(max_heap.pop(), Some(90));
    assert_eq!(max_heap.pop(), Some(80));

    // 2. Top-3 largest elements using a bounded Min-Heap (`Reverse`):
    let data = [15, 92, 4, 78, 33, 105, 61, 88];
    let top3 = top_k_largest(&data, 3);
    assert_eq!(top3, vec![88, 92, 105]);

    println!("Top 3 largest values: {top3:?}");
}

Top 3 largest values: [88, 92, 105]