Min-Heap Using Reverse<T>

Because std::collections::BinaryHeap<T> is a max-heap, wrapping its elements in the standard library adapter std::cmp::Reverse<T> (BinaryHeap<Reverse<T>>) inverts the comparison order and turns BinaryHeap into a min-heap that always keeps the smallest element at the top.

How BinaryHeap<Reverse<T>> Works

Standard `BinaryHeap<i32>` (Max-Heap):
  Root = 90  (pops: 90, 50, 10)

`BinaryHeap<Reverse<i32>>` (Min-Heap):
  Root = Reverse(10)  (pops: Reverse(10), Reverse(50), Reverse(90))

1. Pushing: Wrap each element in Reverse(val) when calling heap.push(Reverse(val)).
2. Popping and Peeking: Destructure Reverse(val) directly inside while let Some(Reverse(val)) = heap.pop() or if let Some(&Reverse(val)) = heap.peek().

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

fn main() {
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();

    for n in [40, 10, 90, 20, 5] {
        min_heap.push(Reverse(n));
    }

    if let Some(&Reverse(smallest)) = min_heap.peek() {
        println!("Smallest element (.peek()): {smallest}");
    }

    print!("Popping in ascending order: ");
    while let Some(Reverse(val)) = min_heap.pop() {
        print!("{val} ");
    }
    println!();
}

Smallest element (.peek()): 5
Popping in ascending order: 5 10 20 40 90 

Keeping the Top $K$ Largest Elements Using a Bounded Min-Heap

A classic streaming algorithm for finding the $K$ largest elements in a stream of $N$ items ($N \gg K$) uses a min-heap of size $K$ (BinaryHeap<Reverse<T>>):

• The smallest of the top $K$ candidates sits at the root of the min-heap (min_heap.peek_mut()).
• Whenever a new stream item x is larger than that root, replace the root in place (*root = Reverse(x)), keeping memory bounded to $O(K)$ and time to $O(N \log K)$:

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

fn top_k_largest(stream: &[i32], k: usize) -> Vec<i32> {
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::with_capacity(k);

    for &x in stream {
        if min_heap.len() < k {
            min_heap.push(Reverse(x));
        } else if let Some(mut smallest_top) = min_heap.peek_mut() {
            if x > smallest_top.0 {
                *smallest_top = Reverse(x); // Replaces root and sifts down in O(log k)
            }
        }
    }

    let mut result: Vec<i32> = min_heap.into_iter().map(|Reverse(x)| x).collect();
    result.sort_unstable();
    result
}

fn main() {
    let data = [12, 99, 4, 85, 42, 77, 105, 19];
    println!("Top 3 largest: {:?}", top_k_largest(&data, 3));
}

Top 3 largest: [85, 99, 105]