RustBook项目中的二叉堆实现解析

二叉堆(Binary Heap)是一种重要的数据结构，它是一棵完全二叉树，并且满足堆性质：每个节点的值都小于或等于其子节点的值(最小堆)或者大于或等于其子节点的值(最大堆)。本文将深入分析RustBook项目中提供的二叉堆实现，帮助读者理解其核心原理和实现细节。

二叉堆的基本概念

二叉堆通常用于实现优先队列，具有以下特点：

• 完全二叉树结构，可以用数组高效存储
• 堆顶元素总是最小(最小堆)或最大(最大堆)
• 插入和删除操作的时间复杂度为O(log n)

数据结构定义

在RustBook的实现中，二叉堆被定义为：

#[derive(Debug, Clone)]
struct BinaryHeap {
    size: usize,    // 数据量
    data: Vec<i32>, // 数据容器
}

这里使用了Vec<i32>作为底层存储，size记录当前堆中的元素数量。值得注意的是，data的第一个位置(索引0)被预留不使用，这样可以通过简单的位运算来计算父子节点关系。

核心宏定义

实现中定义了三个关键宏来计算节点关系：

// 计算父节点下标
macro_rules! parent {
    ($child:ident) => {
        $child >> 1
    };
}

// 计算左子节点下标
macro_rules! left_child {
    ($parent:ident) => {
        $parent << 1
    };
}

// 计算右子节点下标
macro_rules! right_child {
    ($parent:ident) => {
        ($parent << 1) + 1
    };
}

这些宏利用了位运算的高效性：

• 父节点位置 = 子节点位置 / 2 (使用右移运算)
• 左子节点位置 = 父节点位置 * 2 (使用左移运算)
• 右子节点位置 = 父节点位置 * 2 + 1

主要操作实现

插入操作(push)

插入操作遵循以下步骤：

1. 将新元素添加到数组末尾
2. 执行"上浮"操作调整堆结构

fn push(&mut self, val: i32) {
    self.data.push(val);
    self.size += 1;
    self.move_up(self.size);
}

删除操作(pop)

删除操作(通常删除堆顶元素)：

1. 交换堆顶和最后一个元素
2. 移除最后一个元素(原堆顶)
3. 对新的堆顶执行"下沉"操作

fn pop(&mut self) -> Option<i32> {
    if 0 == self.size {
        None
    } else if 1 == self.size {
        self.size -= 1;
        self.data.pop()
    } else {
        self.data.swap(1, self.size);
        let val = self.data.pop();
        self.size -= 1;
        self.move_down(1);
        val
    }
}

堆调整操作

上浮(move_up)

当子节点比父节点小时，需要交换它们的位置：

fn move_up(&mut self, mut c: usize) {
    loop {
        let p = parent!(c);
        if p <= 0 { break; }
        
        if self.data[c] < self.data[p] {
            self.data.swap(c, p);
        }
        
        c = p;
    }
}

下沉(move_down)

当父节点比子节点大时，需要与较小的子节点交换：

fn move_down(&mut self, mut c: usize) {
    loop {
        let lc = left_child!(c);
        if lc > self.size { break; }
        
        let mc = self.min_child(c);
        
        if self.data[c] > self.data[mc] {
            self.data.swap(c, mc);
        }
        
        c = mc;
    }
}

构建堆的两种方式

实现中提供了两种构建堆的方法：

1. 逐个添加法：通过多次调用push方法构建堆

fn build_add(&mut self, arr: &[i32]) {
    for &val in arr {
        self.push(val);
    }
}

2. 整体构建法：先填充所有元素，然后从最后一个非叶子节点开始调整

fn build_new(&mut self, arr: &[i32]) {
    // 清空原有数据
    for _i in 0..self.size {
        let _rm = self.data.pop();
    }

    // 添加新数据
    for &val in arr {
        self.data.push(val);
    }
    self.size = arr.len();

    // 从最后一个非叶子节点开始调整
    let size = self.size;
    let mut p = parent!(size);
    while p > 0 {
        self.move_down(p);
        p -= 1;
    }
}

整体构建法的时间复杂度为O(n)，比逐个添加法的O(n log n)更高效。

实际应用示例

fn main() {
    let mut bh = BinaryHeap::new();
    let nums = [-1,0,2,3,4];
    
    // 测试push操作
    bh.push(10); bh.push(9);
    bh.push(8); bh.push(7); bh.push(6);

    // 测试build_add
    bh.build_add(&nums);
    println!("empty: {:?}", bh.is_empty());
    println!("min: {:?}", bh.min());
    println!("pop min: {:?}", bh.pop());

    // 测试build_new
    bh.build_new(&nums);
    println!("size: {:?}", bh.len());
    println!("pop min: {:?}", bh.pop());
}

总结

RustBook中的二叉堆实现展示了以下关键点：

1. 使用数组存储完全二叉树的高效性
2. 通过位运算快速计算节点关系的技巧
3. 堆调整的核心算法(上浮和下沉)
4. 两种不同的堆构建方法及其性能差异

这个实现可以作为学习Rust数据结构的优秀范例，读者可以在此基础上扩展功能，如支持泛型、实现最大堆等。理解二叉堆的实现原理对于掌握更复杂的优先队列和堆排序算法至关重要。