Binary Heap Priority Queues

In this lesson, you will learn how to implement efficient task scheduling by leveraging Rust’s BinaryHeap to manage elements based on their relative priority rather than their insertion order.

The Binary Heap Concept

A BinaryHeap is a specialized collection that maintains a "max-heap" property. Unlike a Vec or VecDeque, which are linear, a BinaryHeap is conceptually a tree where the largest element is always positioned at the "root" (the front of the queue). Because it is implemented as a contiguous array, it provides excellent cache locality—fitting perfectly with our previous lessons on memory layout and heap allocation efficiency.

In Rust, std::collections::BinaryHeap gives us $O(\log n)$ insertion and removal of the maximum element. This makes it the ideal backbone for a task scheduler where you need to repeatedly extract the "highest priority" work item.

Implementing a Priority Scheduler

To make custom objects work with a priority queue, they must implement Ord. Since Rust’s BinaryHeap is a max-heap by default, it will automatically bubble the item with the highest value to the top.

use std::collections::BinaryHeap;

#[derive(Debug, Eq, PartialEq)]
struct Task {
    priority: u32,
    name: &'static str,
}

// Implement Ord to define our priority logic
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<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut scheduler = BinaryHeap::new();
    scheduler.push(Task { priority: 1, name: "Low Priority" });
    scheduler.push(Task { priority: 10, name: "Critical" });

    // Returns the task with the highest priority first
    if let Some(task) = scheduler.pop() {
        println!("Processing: {}", task.name);
    }
}

By storing tasks in the heap, we ensure that as the collection grows, our performance remains highly predictable. Even as we push new tasks, the heap rebalances itself in-place, keeping memory overhead minimal and avoiding the expensive re-sorting required by a standard Vec.

Key Takeaway: Use BinaryHeap when you need to repeatedly access the highest-priority element while maintaining efficient $O(\log n)$ performance for dynamic additions and removals.