深入理解Rust中的堆（Heap）

为什么选择堆？

堆在很多场景中非常有用，比如：

• 任务调度系统（优先级高的任务先执行）
• 图算法中的 Dijkstra 最短路径
• 流数据中动态获取第 K 小/大元素
• 堆排序算法 的核心组件

用数组表示完全二叉树

堆通常基于完全二叉树实现，而完全二叉树可以用数组高效存储。假设根节点索引为 0，则：

• 父节点索引：parent(i) = (i - 1) / 2
• 左子节点索引：left(i) = 2 * i + 1
• 右子节点索引：right(i) = 2 * i + 2

Rust 实现最小堆

下面是一个完整的 Rust堆数据结构 实现，支持插入、弹出最小值和查看堆顶元素。

struct MinHeap {    data: Vec<i32>,}impl MinHeap {    // 创建空堆    fn new() -> Self {        MinHeap { data: Vec::new() }    }    // 获取父节点索引    fn parent(i: usize) -> usize {        (i - 1) / 2    }    // 获取左子节点索引    fn left(i: usize) -> usize {        2 * i + 1    }    // 向上调整（维护堆性质）    fn heapify_up(&mut self) {        let mut idx = self.data.len() - 1;        while idx > 0 {            let p = Self::parent(idx);            if self.data[idx] < self.data[p] {                self.data.swap(idx, p);                idx = p;            } else {                break;            }        }    }    // 向下调整    fn heapify_down(&mut self) {        let mut idx = 0;        let len = self.data.len();        loop {            let l = Self::left(idx);            if l >= len {                break;            }            let r = l + 1;            let smallest = if r < len && self.data[r] < self.data[l] {                r            } else {                l            };            if self.data[smallest] < self.data[idx] {                self.data.swap(idx, smallest);                idx = smallest;            } else {                break;            }        }    }    // 插入元素    fn push(&mut self, value: i32) {        self.data.push(value);        self.heapify_up();    }    // 弹出最小元素    fn pop(&mut self) -> Option<i32> {        if self.data.is_empty() {            return None;        }        if self.data.len() == 1 {            return Some(self.data.pop().unwrap());        }        let min = self.data[0];        self.data[0] = self.data.pop().unwrap();        self.heapify_down();        Some(min)    }    // 查看堆顶（不移除）    fn peek(&self) -> Option<&i32> {        self.data.first()    }    // 堆是否为空    fn is_empty(&self) -> bool {        self.data.is_empty()    }}

使用示例

现在我们来测试这个堆：

fn main() {    let mut heap = MinHeap::new();    heap.push(10);    heap.push(5);    heap.push(20);    heap.push(3);    println!("堆顶: {:?}", heap.peek()); // 输出: Some(3)    while !heap.is_empty() {        println!("弹出: {:?}", heap.pop());    }    // 输出顺序: 3, 5, 10, 20}

性能分析

- push 操作：O(log n)

- pop 操作：O(log n)

- peek 操作：O(1)

这使得堆非常适合需要频繁插入和提取最值的场景。

进阶：泛型与比较器

上面的实现仅支持 i32。在真实项目中，你可能希望堆能处理任意类型。可以通过泛型和 Ord trait 实现：

use std::cmp::Ordering;#[derive(Eq, PartialEq)]struct Task {    priority: u8,    name: String,}impl Ord for Task {    fn cmp(&self, other: &Self) -> Ordering {        // 注意：为了最小堆，我们需要反转比较        other.priority.cmp(&self.priority)    }}impl PartialOrd for Task {    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {        Some(self.cmp(other))    }}

这样，你就可以创建 MinHeap<Task> 来管理带优先级的任务了！

总结

通过本教程，你已经掌握了如何在 Rust 中实现一个功能完整的最小堆。堆不仅是 Rust优先队列 的基础，也是许多高效算法（如 堆排序算法）的关键组件。理解 Rust堆数据结构 的内部机制，将帮助你在系统编程和算法设计中做出更优的选择。

提示：Rust 标准库其实已提供 BinaryHeap，默认是最大堆。但亲手实现一次，能让你更深入理解其工作原理！