Heaps

A heap gives you the smallest (or largest) item from a changing group, quickly. It doesn't keep everything sorted. Decide which item you need to look at next, then pick a min-heap or a max-heap.

To keep the k largest values of a stream, a new value can only replace the smallest one you're holding. So use a min-heap of at most k items. After t values, it holds the largest min(k, t) of them, counting duplicates.

pub fn kth_largest(nums: &[i32], k: usize) -> Option<i32> {
    use std::cmp::Reverse;
    use std::collections::BinaryHeap;
    if k == 0 || k > nums.len() {
        return None;
    }
    let mut best = BinaryHeap::with_capacity(k + 1);
    for &x in nums {
        best.push(Reverse(x));
        if best.len() > k {
            best.pop();
        }
    }
    best.peek().map(|x| x.0)
}

After a push there are at most k + 1 items. Popping the smallest leaves exactly the best k. A value you dropped can never beat the ones you kept, as long as values only get added. If values could be deleted, a dropped value might matter again, and this reasoning would break.

It takes O(n log k) time and O(k) extra space. For a one-time answer on a fixed list, sorting or quickselect may be better. A heap shines when you need answers again and again as data arrives. Rust's BinaryHeap is a max-heap; wrapping values in Reverse flips it S10.

To merge k sorted lists, the heap holds the first unused item of each list that isn't empty. Everything left in a list is at least that list's first item. So the smallest first item is the smallest item left overall. Pop it, and move only its list forward. For N items in total, that's O(N log k) time and O(k) space.

Two heaps can track a running median. Every value in the lower half is at most every value in the upper half, and the two sizes differ by at most one. You need both rules.

Practice: LC 215 Kth Largest Element in an Array, LC 703 Kth Largest Element in a Stream, LC 347 Top K Frequent Elements, LC 23 Merge k Sorted Lists, LC 295 Find Median from Data Stream.

Check your understanding: Why a min-heap and not a max-heap, or the other way around? Is each item in the heap a final answer or a candidate waiting its turn? Could something you dropped become useful again after a deletion or a priority change?