Rust语言最小堆实现方法（从零开始掌握Rust优先队列与二叉堆）

什么是堆？

堆是一种特殊的完全二叉树，满足“堆性质”：

• 最小堆：任意节点的值 ≤ 其子节点的值，根节点是最小元素。
• 最大堆：任意节点的值 ≥ 其子节点的值，根节点是最大元素。

在 Rust 中，标准库 std::collections::BinaryHeap 默认实现的是 最大堆。但通过自定义比较逻辑，我们可以轻松将其转换为 最小堆。

方法一：使用标准库 BinaryHeap 实现最小堆

Rust 的 BinaryHeap 是基于最大堆构建的。要实现最小堆，我们可以对元素取反（适用于数值类型），或使用 Reverse 包装器。

推荐方式是使用 std::cmp::Reverse，它会自动反转比较逻辑。

use std::collections::BinaryHeap;use std::cmp::Reverse;fn main() {    let mut min_heap = BinaryHeap::new();    // 插入元素（用 Reverse 包装）    min_heap.push(Reverse(10));    min_heap.push(Reverse(5));    min_heap.push(Reverse(20));    min_heap.push(Reverse(1));    // 弹出最小元素    while let Some(Reverse(value)) = min_heap.pop() {        println!("{}", value);    }    // 输出顺序：1, 5, 10, 20}

这段代码展示了如何使用 Reverse 将 BinaryHeap 转换为 Rust最小堆。这是最简单、最高效的方式，适合大多数应用场景。

方法二：手动实现最小堆（加深理解）

为了深入理解堆的工作原理，我们也可以从零开始实现一个最小堆。我们将使用 Vec<T> 作为底层存储，并实现 push 和 pop 方法。

#[derive(Debug)]pub struct MinHeap {    data: Vec,}impl MinHeap {    pub fn new() -> Self {        MinHeap { data: Vec::new() }    }    pub fn push(&mut self, value: T) {        self.data.push(value);        self.heapify_up(self.data.len() - 1);    }    pub fn pop(&mut self) -> Option {        if self.data.is_empty() {            return None;        }        if self.data.len() == 1 {            return Some(self.data.pop().unwrap());        }        let root = self.data.swap_remove(0);        self.heapify_down(0);        Some(root)    }    fn heapify_up(&mut self, mut idx: usize) {        while idx > 0 {            let parent = (idx - 1) / 2;            if self.data[idx] >= self.data[parent] {                break;            }            self.data.swap(idx, parent);            idx = parent;        }    }    fn heapify_down(&mut self, mut idx: usize) {        loop {            let left = 2 * idx + 1;            let right = 2 * idx + 2;            let mut smallest = idx;            if left < self.data.len() && self.data[left] < self.data[smallest] {                smallest = left;            }            if right < self.data.len() && self.data[right] < self.data[smallest] {                smallest = right;            }            if smallest == idx {                break;            }            self.data.swap(idx, smallest);            idx = smallest;        }    }    pub 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(1);    while !heap.is_empty() {        println!("{:?}", heap.pop().unwrap());    }    // 输出：1, 5, 10, 20}

这个手动实现展示了 Rust二叉堆 的核心逻辑：heapify_up 在插入后维护堆性质，heapify_down 在删除根节点后恢复堆结构。

两种方法对比

总结

通过本文，你已经掌握了在 Rust 中实现 最小堆 的两种主要方法。对于日常开发，推荐使用 BinaryHeap 配合 Reverse，这是官方支持且经过优化的方式。而手动实现则有助于你深入理解 Rust数据结构教程 中的核心概念。

无论你是在准备面试、刷 LeetCode，还是开发高性能系统，掌握 Rust优先队列 的使用都至关重要。希望这篇教程能为你打下坚实基础！

SEO关键词回顾：

• Rust最小堆
• Rust优先队列
• Rust二叉堆
• Rust数据结构教程