第 37 课 - 堆（优先队列）

1. 学习目标

完成本课学习后，你将能够：

理解堆（特别是最大堆和最小堆）的核心性质和数据结构。
掌握使用数组表示堆并计算父子节点索引的方法。
实现堆的两大核心操作：建堆（Heapify）和插入（Insert）。
理解优先队列的概念，并了解如何使用堆来高效实现它。
认识 Python 标准库中的 heapq 模块及其常用操作。

2. 核心概念

什么是堆？ 堆是一种特殊的完全二叉树，它满足一个关键属性——堆有序。

最大堆：对于任意一个节点，它的值总是大于或等于其子节点的值。因此，堆顶（根节点）就是整个堆中的最大值。
最小堆：对于任意一个节点，它的值总是小于或等于其子节点的值。堆顶是最小值。

堆通常使用数组来存储，而不是链表。这种存储方式非常节省空间，因为完全二叉树的节点是连续存储的。对于一个节点（数组索引为 i）：

其父节点索引为 (i - 1) // 2
其左子节点索引为 2 * i + 1
其右子节点索引为 2 * i + 2

什么是优先队列？ 优先队列是一种抽象数据类型，其中每个元素都有一个“优先级”。元素的出队顺序由优先级决定（通常是最高或最低优先级先出），而不是先进先出（FIFO）。堆是实现优先队列最常用且高效的数据结构之一。

核心操作：

建堆：将一个无序数组调整成堆结构。时间复杂度为 O(n)。
插入元素：将新元素放入数组末尾，然后通过“上浮”（bubble-up）操作调整其位置以维持堆的性质。时间复杂度为 O(log n)。
提取堆顶元素：取出堆顶（最大值或最小值），将数组最后一个元素移到堆顶，然后通过“下沉”（bubble-down/sink）操作调整堆。时间复杂度为 O(log n)。

3. 代码示例

下面是一个最小堆（Python 实现）的完整示例，包含了建堆、插入和提取操作。

class MinHeap:
    def __init__(self):
        # 使用数组来存储堆元素
        self.heap = []
        self.size = 0

    def parent(self, i):
        """返回父节点的索引"""
        return (i - 1) // 2

    def left_child(self, i):
        """返回左子节点的索引"""
        return 2 * i + 1

    def right_child(self, i):
        """返回右子节点的索引"""
        return 2 * i + 2

    def swap(self, i, j):
        """交换数组中的两个元素"""
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def insert(self, value):
        """
        插入一个新元素。
        步骤：1. 将元素放到数组末尾。2. 上浮调整。
        """
        # 步骤1：添加到末尾
        self.heap.append(value)
        self.size += 1
        # 步骤2：上浮操作
        self._bubble_up(self.size - 1)

    def _bubble_up(self, i):
        """上浮操作：将索引 i 处的元素向上移动，直到堆性质恢复"""
        # 当前节点不是根节点，并且它的值小于其父节点的值
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            self.swap(i, self.parent(i))
            i = self.parent(i)

    def extract_min(self):
        """
        提取并返回堆中的最小值。
        步骤：1. 保存堆顶。2. 将末尾元素移到堆顶。3. 下沉调整。
        """
        if self.size == 0:
            raise IndexError("Heap is empty")
        # 步骤1：保存堆顶
        min_val = self.heap[0]
        # 步骤2：将最后一个元素移到堆顶
        self.heap[0] = self.heap[self.size - 1]
        self.heap.pop()
        self.size -= 1
        # 步骤3：下沉操作
        if self.size > 0:
            self._bubble_down(0)
        return min_val

    def _bubble_down(self, i):
        """下沉操作：将索引 i 处的元素向下移动，直到堆性质恢复"""
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)

        # 如果左子节点存在且比当前最小值小，则更新 smallest
        if left < self.size and self.heap[left] < self.heap[smallest]:
            smallest = left
        # 如果右子节点存在且比当前最小值小，则更新 smallest
        if right < self.size and self.heap[right] < self.heap[smallest]:
            smallest = right

        # 如果 smallest 不是当前节点 i，则交换并继续下沉
        if smallest != i:
            self.swap(i, smallest)
            self._bubble_down(smallest)

    def build_heap(self, array):
        """从一个数组构建堆"""
        self.heap = array[:]
        self.size = len(array)
        # 从最后一个非叶子节点开始，依次向前执行下沉操作
        for i in range(self.size // 2 - 1, -1, -1):
            self._bubble_down(i)

# 使用示例
if __name__ == "__main__":
    # 测试插入和提取
    min_heap = MinHeap()
    data = [5, 3, 8, 1, 2, 7]
    for num in data:
        min_heap.insert(num)
    print("插入元素后的堆数组:", min_heap.heap)
    print("提取最小值:", min_heap.extract_min())
    print("提取后的堆数组:", min_heap.heap)

    # 测试建堆
    print("\n--- 测试建堆 ---")
    unsorted_arr = [4, 10, 3, 5, 1]
    min_heap.build_heap(unsorted_arr)
    print("建堆后的堆数组:", min_heap.heap)
    print("依次提取所有元素（堆排序效果）:")
    while min_heap.size > 0:
        print(min_heap.extract_min(), end=' ')

输出示例：

插入元素后的堆数组: [1, 2, 7, 5, 3, 8]
提取最小值: 1
提取后的堆数组: [2, 3, 7, 5, 8]

--- 测试建堆 ---
建堆后的堆数组: [1, 4, 3, 5, 10]
依次提取所有元素（堆排序效果）:
1 3 4 5 10

4. 实践练习

练习 1：最小堆遍历 在上面的 MinHeap 类中添加一个 display 方法，能够层次遍历并打印堆中的所有元素（每行一层）。

预期输出示例（对于堆 [1, 3, 2, 7, 6]）：

Level 0: 1
Level 1: 3, 2
Level 2: 7, 6

练习 2：实现最大堆 参考 MinHeap 类，创建一个 MaxHeap 类。所有比较逻辑需要反转（确保堆顶是最大值）。编写测试代码，插入 [5, 3, 8, 1, 2, 7] 并依次提取，验证输出顺序为从大到小。

练习 3：堆排序 使用你之前实现的 build_heap 和 extract_min 方法（或者新建一个 MaxHeap 并用其 extract_max 方法），实现一个函数 heap_sort(arr)，对输入数组进行升序排序。在函数内部，不应直接调用 sorted 或 .sort()。

输入: [4, 10, 3, 5, 1]
预期输出: [1, 3, 4, 5, 10]

5. 常见错误

索引计算错误：父子节点索引公式 (i-1)//2, 2*i+1, 2*i+2 是基于0-indexed数组的。这是初学者最容易犯错的地方，尤其是在纸上推导时。
下沉操作遗漏子节点比较：在 _bubble_down 中，必须同时与左、右子节点比较，并选择三者中的最小值（最小堆）进行交换。忘记比较其中一个子节点会导致错误。
忘记处理空堆或单个元素：在 extract_min 中，如果堆为空，应抛出异常；当提取后堆只剩一个元素时，无需执行下沉操作。
建堆的起始位置：建堆时，循环应从最后一个非叶子节点开始（即索引 self.size // 2 - 1），并向前递减。从数组中部或开头开始是无效的。

6. 小结

堆是一个满足堆有序性质的完全二叉树，通常用数组实现，效率高且节省空间。
最大堆堆顶是最大值，最小堆堆顶是最小值。父子节点索引关系是堆操作的基础。
核心操作的时间复杂度：
- 建堆 (Heapify): O(n)
- 插入 (Insert): O(log n)
- 提取极值 (Extract): O(log n)
优先队列是一种按优先级出队的抽象数据结构，堆是其经典且高效的实现。
Python 标准库的 heapq 模块实现了最小堆，提供了 heappush, heappop, heapify 等便捷函数，可以直接用于优先队列场景。
应用场景：堆常用于实现优先队列、堆排序算法、图算法（如Dijkstra, Prim）中获取最小/最大值、实时数据流的中位数查找等。

练习编辑器

rust