Rust双端优先级队列库interval-heap使用指南

interval-heap是Rust中一个高效的双端优先级队列实现，它同时支持最小堆和最大堆操作，允许你高效地访问和移除队列中的最小和最大元素。

特性

• 同时支持O(1)时间的最小值和最大值访问
• 插入和删除操作的时间复杂度为O(log n)
• 实现了Rust标准库的std::collections中的常见接口
• 完全安全的Rust实现

使用方法

添加依赖

首先在Cargo.toml中添加依赖：

[dependencies]
interval-heap = "1.0"

基本操作示例

use interval_heap::IntervalHeap;

fn main() {
    // 创建一个空的双端优先级队列
    let mut heap = IntervalHeap::new();
    
    // 插入元素
    heap.push(3);
    heap.push(1);
    heap.push(4);
    heap.push(1);
    heap.push(5);
    heap.push(9);
    
    // 查看最小元素
    println!("Min: {:?}", heap.peek_min()); // 输出: Min: Some(1)
    
    // 查看最大元素
    println!("Max: {:?}", heap.peek_max()); // 输出: Max: Some(9)
    
    // 弹出最小元素
    let min = heap.pop_min();
    println!("Popped min: {:?}", min); // 输出: Popped min: Some(1)
    
    // 弹出最大元素
    let max = heap.pop_max();
    println!("Popped max: {:?}", max); // 输出: Popped max: Some(9)
    
    // 迭代所有元素(无序)
    for num in &heap {
        println!("{}", num); // 可能输出: 3, 1, 4, 5 (顺序不确定)
    }
}

从现有数据构建堆

use interval_heap::IntervalHeap;

fn main() {
    let data = vec![5, 3, 8, 1, 2, 7];
    let heap: IntervalHeap<_> = data.into_iter().collect();
    
    println!("Min: {}", heap.peek_min().unwrap()); // 1
    println!("Max: {}", heap.peek_max().unwrap()); // 8
}

自定义比较逻辑

use interval_heap::IntervalHeap;
use std::cmp::Reverse;

fn main() {
    // 使用Reverse包装类型来反转比较顺序
    let mut heap = IntervalHeap::new();
    
    heap.push(Reverse(5));
    heap.push(Reverse(3));
    heap.push(Reverse(8));
    
    // 现在peek_min会返回最大的原始值
    println!("Min (original max): {:?}", heap.peek_min().unwrap().0); // 8
    
    // 也可以自定义结构体和Ord实现
    #[derive(Debug, PartialEq, Eq)]
    struct Task {
        priority: u32,
        description: String,
    }
    
    impl PartialOrd for Task {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            self.priority.partial_cmp(&other.priority)
        }
    }
    
    impl Ord for Task {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            self.priority.cmp(&other.priority)
        }
    }
    
    let mut task_heap = IntervalHeap::new();
    task_heap.push(Task {
        priority: 3,
        description: "Low priority task".to_string(),
    });
    task_heap.push(Task {
        priority: 1,
        description: "High priority task".to_string(),
    });
    
    println!("Next task: {:?}", task_heap.peek_min().unwrap().description); // "High priority task"
}

性能考虑

interval-heap在需要同时访问最小和最大元素的场景下特别高效。与使用两个独立堆(一个最小堆和一个最大堆)相比，interval-heap:

• 使用更少的内存(约节省50%)
• 保持数据一致性更简单
• 插入操作只需要一次而不是两次

对于只需要单一方向(只需最小或只需最大)优先级队列的场景，标准的BinaryHeap可能更合适。

其他实用方法

use interval_heap::IntervalHeap;

fn main() {
    let mut heap = IntervalHeap::from(vec![5, 1, 3, 4, 2]);
    
    // 检查堆是否为空
    println!("Is empty: {}", heap.is_empty()); // false
    
    // 获取堆中元素数量
    println!("Length: {}", heap.len()); // 5
    
    // 清空堆
    heap.clear();
    println!("Length after clear: {}", heap.len()); // 0
    
    // 保留满足条件的元素
    let mut heap = IntervalHeap::from(vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    heap.retain(|&x| x % 2 == 0); // 只保留偶数
    println!("Remaining items: {:?}", heap.into_sorted_vec()); // [2, 4, 6, 8]
}

完整示例代码

use interval_heap::IntervalHeap;
use std::cmp::Reverse;

fn main() {
    // 示例1: 基本操作
    let mut heap = IntervalHeap::new();
    heap.push(3);
    heap.push(1);
    heap.push(4);
    
    println!("Min: {:?}", heap.peek_min()); // Some(1)
    println!("Max: {:?}", heap.peek_max()); // Some(4)
    
    // 示例2: 从集合构建
    let data = vec![5, 2, 8, 3];
    let heap2: IntervalHeap<_> = data.into_iter().collect();
    println!("From collection min: {}", heap2.peek_min().unwrap()); // 2
    
    // 示例3: 自定义排序
    let mut reverse_heap = IntervalHeap::new();
    reverse_heap.push(Reverse(5));
    reverse_heap.push(Reverse(2));
    println!("Reverse min: {:?}", reverse_heap.peek_min().unwrap().0); // 5
    
    // 示例4: 任务调度
    #[derive(Debug, Eq, PartialEq)]
    struct Job {
        priority: i32,
        name: String,
    }
    
    impl Ord for Job {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            self.priority.cmp(&other.priority)
        }
    }
    
    impl PartialOrd for Job {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(other))
        }
    }
    
    let mut job_queue = IntervalHeap::new();
    job_queue.push(Job {
        priority: 1,
        name: "Urgent".to_string(),
    });
    job_queue.push(Job {
        priority: 3,
        name: "Normal".to_string(),
    });
    
    println!("Next job: {:?}", job_queue.peek_min().unwrap().name); // "Urgent"
    
    // 示例5: 实用方法
    let mut nums = IntervalHeap::from(vec![1, 4, 2, 3]);
    nums.retain(|&x| x > 2);
    println!("Filtered: {:?}", nums.into_sorted_vec()); // [3, 4]
}

interval-heap为需要双端优先级队列的场景提供了一个高效且易于使用的解决方案，特别适合需要频繁访问和操作队列两端元素的算法和应用。