I've been thinking about how to handle a task scheduler for a simulation I'm working on. I have a bunch of events that need to happen, but they aren't all equal. Some are critical system interrupts that need to happen now, and others are just background cleanup tasks. My first instinct was to just throw them in a Vec and sort it, but that felt... clumsy. Let's see how that actually looks in code first.

The sorting bottleneck

struct Task {
    priority: i32,
    description: String,
}

fn main() {
    let mut tasks = Vec::new();
    tasks.push(Task { priority: 10, description: "Low priority cleanup".into() });
    tasks.push(Task { priority: 100, description: "CRITICAL ERROR".into() });
    tasks.push(Task { priority: 50, description: "User input".into() });

    // To get the highest priority, I have to sort the whole thing
    tasks.sort_by(|a, b| b.priority.cmp(&a.priority));
    
    if let Some(top_task) = tasks.pop() {
        println!("Executing: {}", top_task.description);
    }
}

Wait, I just realized a huge problem here. If I'm adding tasks constantly while the program is running, I'd have to call sort_by every single time I push a new element if I want to maintain that order. That's an $O(n \log n)$ operation just to add one item. In a high-performance system, that's a non-starter. I need something that keeps the "most important" item at the top without me having to manually reorganize the whole list.

Switching to a BinaryHeap

This is exactly where std::collections::BinaryHeap comes in. It's essentially a priority queue. Instead of a linear list, it uses a tree structure (a max-heap) to ensure that the element with the greatest value is always at the front. Let's swap the Vec for a BinaryHeap and see what happens.

use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Task {
    priority: i32,
    description: String,
}

// We need to implement Ord and PartialOrd so the heap knows how to compare Tasks
impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&other.priority)
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Task { priority: 10, description: "Low priority cleanup".into() });
    heap.push(Task { priority: 100, description: "CRITICAL ERROR".into() });
    heap.push(Task { priority: 50, description: "User input".into() });

    while let Some(task) = heap.pop() {
        println!("Executing: {} (Priority: {})", task.description, task.priority);
    }
}

That's much better. The push and pop operations are now $O(\log n)$. But notice something about the output: it gave me the "CRITICAL ERROR" (100) first. That's because BinaryHeap is a max-heap by default. It always pops the largest value.

The "Lowest Number is Highest Priority" Problem

In many real-world APIs, "Priority 1" is the most urgent, and "Priority 10" is the least. If I use the code above with that logic, my most urgent tasks will actually be the last ones to execute. I can't just change the Ord implementation to be reversed because that might confuse other parts of my code that expect standard integer comparison.

The idiomatic Rust way to handle this without rewriting my Ord logic is to use std::cmp::Reverse. It's a little wrapper that flips the result of any comparison.

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

fn main() {
    // We store a tuple of (priority, description)
    // We wrap the priority in Reverse() to turn the max-heap into a min-heap
    let mut heap = BinaryHeap::new();

    heap.push(Reverse((10, "Low priority cleanup")));
    heap.push(Reverse((1, "URGENT: System Failure")));
    heap.push(Reverse((5, "User input")));

    while let Some(Reverse((priority, desc))) = heap.pop() {
        println!("Executing: {} (Priority: {})", desc, priority);
    }
}

Now, the task with priority 1 comes out first. By wrapping the value in Reverse, I've effectively told the BinaryHeap: "Whenever you compare these two items, act as if the smaller number is actually the larger one." It's a clean way to get a min-heap without fighting the standard library.

📋 Practical Task

Project: Emergency Room Triage System

Build a triage system for a hospital emergency room. You need to create a program that manages a queue of patients based on their severity level.

• Define a Patient struct with a name (String) and a severity (integer, where 1 is the most critical/urgent and 5 is the least).
• Implement the necessary traits (Eq, PartialEq, Ord, PartialOrd) so that patients can be compared based on their severity.
• Use a BinaryHeap to store the patients. Ensure that when you pop() from the heap, the patient with the lowest severity number (the most urgent) is returned first.
• Add at least five patients with varying severity levels and names to the heap in random order.
• Print the patients in the order they should be treated.