Module 4Priority Queue (BinaryHeap)Lesson 19 of 2320 min

Min-Heap with Reverse

std::cmp::Reverse wrapper — critical interview trick in Rust.

Min-heap

rust

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

fn main() {
    let mut h = BinaryHeap::new();
    h.push(Reverse(3));
    h.push(Reverse(1));
    h.push(Reverse(5));
    println!("pop min={:?}", h.pop()); // Some(Reverse(1))
    println!("next min value={}", h.peek().unwrap().0);
}

Output

pop min=Some(Reverse(1))
next min value=3

Top-K pattern

Keep a min-heap of size k of the largest elements:

push next

if len > k, pop (drops current smallest of the large ones)

heap then holds k largest; peek is kth largest

Challenge

Merge k sorted lists conceptually: heap of (value, list_id, idx).

Tips

Reverse(x) for min-heap
Top-k uses size-k heap
.0 to unwrap Reverse

Try it live

Min-Heap with ReverseRust 2021

Loading editor…

Output

Press Run to compile and execute.