RustArena

Step 3 of 6

Priority queues with BinaryHeap

A priority queue hands out the most important item first, not the oldest one: the patient in the worst condition, the job with the highest priority, the closest unvisited city. In Rust that's std::collections::BinaryHeap<T>, a max-heap: pop always returns the largest item.

Inside, it's a Vec arranged as a binary heap: a tree stored in an array where every parent is at least as large as its children. Keeping that shape after a change only walks one branch of the tree, so push and pop are O(log n) and peek is O(1). (log n grows very slowly: about 20 for a million items.)

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    for severity in [3, 9, 1, 7] {
        heap.push(severity);
    }
    println!("peek: {:?}", heap.peek());
    println!("len: {}", heap.len());
    while let Some(s) = heap.pop() {
        print!("{s} ");
    }
    println!();
}

peek: Some(9)
len: 4
9 7 3 1

A min-heap with Reverse

To get the smallest item first, wrap values in std::cmp::Reverse. Reverse(x) is a tiny struct whose ordering is the opposite of x's, so the "largest" Reverse holds the smallest value. Unwrap it with .0 or with a pattern:

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

fn main() {
    let mut deadlines = BinaryHeap::new();
    for day in [12, 3, 30, 7] {
        deadlines.push(Reverse(day));
    }
    println!("soonest: {}", deadlines.peek().unwrap().0);
    while let Some(Reverse(day)) = deadlines.pop() {
        print!("{day} ");
    }
    println!();
}

soonest: 3
3 7 12 30

Tuples as priorities

Tuples compare field by field: first fields first, and only on a tie the second, and so on. That makes them perfect priority keys. In an emergency room, higher severity goes first, and between equal severities whoever arrived first. "Arrived first" means the smaller arrival number should win, so it's wrapped in Reverse:

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

fn main() {
    // (severity, Reverse(arrival), case)
    let mut er = BinaryHeap::new();
    er.push((2, Reverse(1), "sprained ankle"));
    er.push((5, Reverse(2), "chest pain"));
    er.push((2, Reverse(3), "deep cut"));
    er.push((5, Reverse(4), "broken leg"));
    while let Some((severity, Reverse(arrival), case)) = er.pop() {
        println!("{severity} #{arrival} {case}");
    }
}

5 #2 chest pain
5 #4 broken leg
2 #1 sprained ankle
2 #3 deep cut

A struct works too: #[derive(PartialEq, Eq, PartialOrd, Ord)] compares fields in the order they're declared, or you implement Ord yourself (module 23).

Top-k with a small heap

To keep the k largest of n values, you don't need to sort all n. Keep a min-heap of at most k items: push each value, and when the heap holds more than k, pop (that removes the smallest). What's left are the k largest. That's O(n log k) time and O(k) memory, and it works on a stream of data that never fits in memory at once.

Common mistakes

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(2.5_f64);
    println!("{:?}", heap.pop());
}

error[E0277]: the trait bound `f64: Ord` is not satisfied

Store integers instead (cents, milliseconds, scores times 100), or wrap the float in your own type that implements Ord with total_cmp.

Your task

Write fn top_k(scores: &[u32], k: usize) -> Vec<u32> that returns the k highest scores, highest first (all of them if there are fewer than k). Use a BinaryHeap<Reverse<u32>> that never holds more than k items, then pop it empty and reverse. Don't sort.

Challenge 2

Several services each write a log already sorted by timestamp. Merge them into one sorted list. Write fn merge_sorted(lists: &[Vec<i32>]) -> Vec<i32>.

Concatenating and sorting would work, but the classic approach uses the fact that each list is already sorted: keep a min-heap with the next item of each list as Reverse((value, list_index, position)). Pop the smallest, add it to the result, and push the following item from the same list. With N items in k lists that's O(N log k). Don't sort.

Challenge 3

Write a job scheduler. Standard input has one job per line: a name and a priority from 1 to 9, like deploy 9. Process the jobs highest priority first; jobs with the same priority run in the order they were submitted. Print one line per job:

1. deploy (p9)
2. backup (p5)

Use a BinaryHeap. The trick for "first submitted first" is the one from the emergency room: push (priority, Reverse(line_number), name). Skip blank lines.

Previous: Queues with VecDeque Next: Range queries with BTreeMap and BTreeSet