pop_first() and pop_last()

The .pop_first() and .pop_last() methods on BTreeMap<K, V> and BTreeSet<T> remove and return the minimum or maximum element in $O(\log n)$ time, enabling BTreeMap and BTreeSet to act as double-ended priority queues with unique keys.

Signatures

// On BTreeMap<K, V>:
pub fn pop_first(&mut self) -> Option<(K, V)>;
pub fn pop_last(&mut self) -> Option<(K, V)>;

// On BTreeSet<T>:
pub fn pop_first(&mut self) -> Option<T>;
pub fn pop_last(&mut self) -> Option<T>;

Using BTreeSet as a Double-Ended Priority Queue (Min-Max Queue)

Unlike BinaryHeap<T>, which only supports popping from one end (.pop() removes the maximum) and allows duplicate entries, BTreeSet<T> supports popping both the minimum (.pop_first()) and the maximum (.pop_last()) in $O(\log n)$ time while automatically deduplicating elements:

use std::collections::BTreeSet;

fn main() {
    let mut job_priorities = BTreeSet::from([10, 50, 25, 90, 40]);

    // Pop the highest-priority job (largest):
    println!("Highest priority popped: {:?}", job_priorities.pop_last());

    // Pop the lowest-priority job (smallest):
    println!("Lowest priority popped:  {:?}", job_priorities.pop_first());

    println!("Remaining jobs:          {job_priorities:?}");
}

Highest priority popped: Some(90)
Lowest priority popped:  Some(10)
Remaining jobs:          {25, 40, 50}

Timer Wheel / Event Scheduler Loop with BTreeMap::pop_first()

Because BTreeMap::pop_first() always extracts the earliest timestamp key (timestamp, task), driving an event loop in chronological order is a simple while let Some((time, event)) = schedule.pop_first() loop:

use std::collections::BTreeMap;

fn main() {
    let mut schedule = BTreeMap::from([
        (300_u64, "send_summary"),
        (100, "connect_db"),
        (200, "run_migrations"),
    ]);

    while let Some((timestamp_ms, action)) = schedule.pop_first() {
        println!("@{timestamp_ms}ms -> executing '{action}'");
        if action == "connect_db" {
            // Dynamically schedule a follow-up task during execution:
            schedule.insert(150, "verify_schema");
        }
    }
}

@100ms -> executing 'connect_db'
@150ms -> executing 'verify_schema'
@200ms -> executing 'run_migrations'
@300ms -> executing 'send_summary'