Ch 14: BinaryHeap优先队列

1. 引言

BinaryHeap是Rust提供的优先队列实现，基于二叉堆数据结构。它是一种最大堆（Max Heap），父节点的键值总是大于或等于其子节点的键值。

主要应用场景：

• 任务调度：优先级高的任务先执行
• Dijkstra最短路径：每次取最小距离的节点
• Top-K问题：高效找出最大的K个元素
• 事件模拟：按时间顺序处理事件

2. 基本操作

2.1 创建与push

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();

    // push 添加元素
    heap.push(3);
    heap.push(1);
    heap.push(4);
    heap.push(1);
    heap.push(5);

    println!("堆大小: {}", heap.len());
    // 输出: 堆大小: 5
}

2.2 pop弹出最大值

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(3);
    heap.push(1);
    heap.push(4);
    heap.push(1);
    heap.push(5);

    // pop 弹出并返回最大值（如果存在）
    while let Some(max) = heap.pop() {
        println!("pop: {}", max);
    }
    // 输出: 5, 4, 3, 1, 1 (不一定按此顺序)
}

注意：BinaryHeap是最大堆，pop返回的是最大的元素，而非最小的。

2.3 peek查看最大值

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(3);
    heap.push(1);
    heap.push(4);

    // peek 查看最大值但不删除
    if let Some(&max) = heap.peek() {
        println!("最大值: {}", max);
        // 输出: 最大值: 4
    }

    println!("pop后peek: {:?}", heap.peek());
    // 输出: pop后peek: Some(4) - peek返回&T，需要解引用
}

3. 使用自定义类型

默认BinaryHeap使用std::cmp::Reverse实现最小堆：

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

fn main() {
    // 最小堆：使用Reverse包装
    let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();

    min_heap.push(Reverse(3));
    min_heap.push(Reverse(1));
    min_heap.push(Reverse(4));

    // pop返回最小值
    if let Some(Reverse(min)) = min_heap.pop() {
        println!("最小值: {}", min);
        // 输出: 最小值: 1
    }
}

3.1 复杂类型的比较

use std::collections::BinaryHeap;

#[derive(Debug)]
struct Task {
    priority: u8,
    name: String,
}

impl PartialEq for Task {
    fn eq(&self, other: &Self) -> bool {
        self.priority == other.priority
    }
}

impl Eq for Task {}

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

impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // 优先级高的排在前面（最大堆）
        other.priority.cmp(&self.priority)
    }
}

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Task { priority: 3, name: String::from("低优先级") });
    heap.push(Task { priority: 1, name: String::from("紧急") });
    heap.push(Task { priority: 5, name: String::from("非常高") });

    // 先处理紧急任务
    if let Some(task) = heap.pop() {
        println!("处理任务: {:?}", task);
        // 输出: 处理任务: Task { priority: 5, name: "非常高" }
    }
}

4. into_iter_sorted有序迭代

into_iter_sorted将堆转换为有序迭代器，按从大到小顺序遍历：

use std::collections::BinaryHeap;

fn main() {
    let heap: BinaryHeap<i32> = [3, 1, 4, 1, 5, 9, 2, 6].into_iter().collect();

    // into_iter_sorted 按从大到小顺序迭代
    println!("有序输出:");
    for item in heap.into_iter_sorted() {
        print!("{} ", item);
    }
    // 输出: 9 6 5 4 3 2 1 1
    println!();
}

注意：into_iter_sorted需要O(n log n)时间复杂度，因为它实际上是堆排序实现。

5. 实用示例：Top-K问题

找出数组中最大的K个元素：

use std::collections::BinaryHeap;

fn top_k(arr: &[i32], k: usize) -> Vec<i32> {
    let mut heap: BinaryHeap<i32> = arr.iter().cloned().collect();

    let mut result = Vec::with_capacity(k);
    for _ in 0..k {
        if let Some(item) = heap.pop() {
            result.push(item);
        }
    }
    result
}

fn main() {
    let arr = [1, 5, 2, 8, 3, 9, 1, 7];
    println!("Top 3: {:?}", top_k(&arr, 3));
    // 输出: Top 3: [9, 8, 7] (顺序可能不同)
}

6. 实用示例：合并有序文件

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

#[derive(Debug)]
struct FileIter {
    name: String,
    current: i32,
    remaining: Vec<i32>,
}

impl FileIter {
    fn new(name: &str, data: Vec<i32>) -> Self {
        let current = data.first().copied().unwrap_or(i32::MAX);
        FileIter {
            name: name.to_string(),
            current,
            remaining: data,
        }
    }
}

impl PartialEq for FileIter {
    fn eq(&self, other: &Self) -> bool {
        self.current == other.current
    }
}

impl Eq for FileIter {}

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

impl Ord for FileIter {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // 最小堆：current小的先出
        self.current.cmp(&other.current)
    }
}

fn main() {
    // 模拟三个有序文件
    let files = vec![
        FileIter::new("file1", vec![1, 3, 5, 7]),
        FileIter::new("file2", vec![2, 4, 8]),
        FileIter::new("file3", vec![0, 6, 9]),
    ];

    let mut heap: BinaryHeap<Reverse<FileIter>> = files
        .into_iter()
        .map(Reverse)
        .collect();

    println!("合并后的有序序列:");
    while let Some(Reverse(mut file_iter)) = heap.pop() {
        print!("{} ", file_iter.current);

        if let Some(next) = file_iter.remaining.get(1).copied() {
            file_iter.current = next;
            file_iter.remaining.remove(0);
            heap.push(Reverse(file_iter));
        }
    }
    // 输出: 0 1 2 3 4 5 6 7 8 9
    println!();
}

7. 性能特点

操作	时间复杂度
push	O(log n)
pop	O(log n)
peek	O(1)
into_iter_sorted	O(n log n)

BinaryHeap的优势：

• 快速获取最大/最小元素：O(1)
• 插入和删除：O(log n)
• 适合优先队列、Top-K、排序等场景

8. 注意事项

1. BinaryHeap是最大堆：pop返回最大元素。如需最小堆，使用Reverse包装。
2. 不保证相同元素的相对顺序：相同优先级的元素，pop顺序不确定。
3. 必须是可比较的类型：元素必须实现Ord trait。

9. 总结

今天我们学习了BinaryHeap优先队列：

1. push - 添加元素到堆中，O(log n)
2. pop - 弹出并返回最大元素，O(log n)
3. peek - 查看最大元素但不删除，O(1)
4. into_iter_sorted - 有序迭代，按从大到小遍历

BinaryHeap是实现优先队列的首选数据结构，在任务调度、算法实现等场景中非常有用。