Part 2.6：堆与优先队列：O(log n) 的动态极值查找

引言：急诊室的“优先处理”

想象一下医院的急诊室，病人络绎不绝地到来，每个人的病情危急程度都不同。护士需要一个高效的系统，来确保在任何时候，都能最快地找到并处理病情最危重的病人。这个系统需要支持两个核心操作：

1. 新病人到达：随时有新病人被送入急诊室。
2. 处理最优先病人：从所有待处理的病人中，立即找出最危急的那一个进行救治。

这个问题，就是优先队列 (Priority Queue) 的经典应用场景。它是一种特殊的队列，出队顺序不是按照“先进先出”（FIFO），而是按照元素的“优先级”。

而实现优先队列最高效的数据结构，就是我们今天要学习的主角——**堆 (Heap)**。

为什么堆如此重要？

• 面试价值：堆是面试中考察数据结构功底的必考点。无论是手写堆的实现，还是应用堆解决 Top K、中位数等问题，都是面试高频题。
• 工程价值：堆是许多高效算法和系统的基石。操作系统的任务调度、网络路由中的最短路径算法（Dijkstra）、数据压缩（霍夫曼编码）以及著名的堆排序，都离不开堆的身影。

本文将带你深入堆的内部，理解其如何通过巧妙的结构，在 O(log n) 的时间内完成插入和删除最大/最小元素的操作。

背景知识：完全二叉树

堆的逻辑结构是一棵**完全二叉树 (Complete Binary Tree)**。

定义：一棵深度为 k 的二叉树，如果它的第 1 到 k-1 层都是满的，并且第 k 层的节点都从左到右连续排列，那么它就是一棵完全二叉树。

关键特性：完全二叉树非常适合用数组来存储。对于数组中索引为 i 的节点：

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

这种用数组表示树的方式，避免了指针的开销，且内存访问是连续的，对缓存非常友好。

详细算法原理

堆分为两种：

• 最大堆 (Max-Heap)：任何一个节点的值，都大于或等于其子节点的值。根节点是整个堆的最大值。
• 最小堆 (Min-Heap)：任何一个节点的值，都小于或等于其子节点的值。根节点是整个堆的最小值。

注意：堆只保证了父子之间的关系，兄弟节点之间的大小关系是不确定的。

1. 核心操作：维护堆的性质

堆的核心在于，当插入或删除元素后，如何通过调整来维持最大堆或最小堆的性质。这依赖于两个基本操作：上浮 (Sift Up) 和 **下沉 (Sift Down)**。

a. 上浮 (Sift Up / Swim)

场景：向堆中插入一个新元素时，新元素需要找到自己合适的位置。

动画式案例： 在最大堆中插入元素 100

图片来源: Wikipedia

步骤解析:

1. 添加到底部：将新元素 100 添加到数组末尾（即完全二叉树的最后一个位置）。
2. 与父节点比较：100 与其父节点 19 比较，100 > 19，不满足最大堆性质。
3. **交换位置 (上浮)**：交换 100 和 19。
4. 继续向上比较：新位置上的 100 继续与其新父节点 36 比较，100 > 36，仍然不满足。
5. 再次上浮：交换 100 和 36。
6. 到达根节点：100 到达根节点，上浮过程结束。

b. 下沉 (Sift Down / Sink)

场景：删除根节点（提取最大/最小值）后，需要从顶部调整，以维持堆的性质。

动画式案例： 从最大堆中删除根节点

图片来源: Wikipedia

步骤解析:

1. 替换根节点：将堆的最后一个元素移动到根节点位置，并删除原来的最后一个元素。
2. 与子节点比较：根节点与其较大的子节点比较。
3. **交换位置 (下沉)**：如果根节点小于其子节点，则交换位置。
4. 继续向下比较：交换后，继续与新的子节点比较，重复下沉，直到当前节点大于其所有子节点，或成为叶子节点。

2. 优先队列的实现

• 插入 (Push)：对应堆的插入操作，时间复杂度 O(log n)。
• 提取最大/最小 (Pop)：对应堆的删除根节点操作，时间复杂度 O(log n)。
• **查看最大/最小 (Peek)**：直接返回数组的第一个元素，时间复杂度 O(1)。

Python 实现

Python 的 heapq 模块提供了一个高效的最小堆实现。我们可以直接使用它，或者为了学习而手写一个。

手写最大堆

class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            raise IndexError("pop from an empty heap")
        
        self._swap(0, len(self.heap) - 1)
        max_val = self.heap.pop()
        self._sift_down(0)
        return max_val

    def peek(self):
        if not self.heap:
            return None
        return self.heap[0]

    def _sift_up(self, index):
        parent_index = (index - 1) // 2
        while index > 0 and self.heap[index] > self.heap[parent_index]:
            self._swap(index, parent_index)
            index = parent_index
            parent_index = (index - 1) // 2

    def _sift_down(self, index):
        n = len(self.heap)
        while True:
            left_child_index = 2 * index + 1
            right_child_index = 2 * index + 2
            largest = index

            if left_child_index < n and self.heap[left_child_index] > self.heap[largest]:
                largest = left_child_index
            
            if right_child_index < n and self.heap[right_child_index] > self.heap[largest]:
                largest = right_child_index

            if largest == index:
                break
            
            self._swap(index, largest)
            index = largest

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

# --- 案例测试 ---
max_heap = MaxHeap()
for num in [3, 1, 4, 1, 5, 9, 2, 6]:
    max_heap.push(num)

print("Max Heap (internal array):", max_heap.heap)

print("Popping elements:")
while max_heap.peek() is not None:
    print(max_heap.pop(), end=" ") # 9 6 5 4 3 2 1 1

复杂度推导过程

设堆中有 n 个元素。

• 时间复杂度：
  • push (插入): O(log n)。上浮操作最多需要交换的次数等于树的高度，即 log₂n。
  • pop (删除): O(log n)。下沉操作最多需要交换的次数也等于树的高度。
  • peek (查看): O(1)。
  • 建堆 (Heapify): O(n)。将一个无序数组构建成一个堆，可以通过从最后一个非叶子节点开始，依次向前执行下沉操作来完成。虽然看起来是 n/2 * log n，但通过严谨的数学证明，其均摊时间复杂度是线性的 O(n)。
• 空间复杂度: O(n)。我们需要一个数组来存储 n 个元素。

优势 / 劣势 / 适用场景

优势

1. 高效的动态极值查找：能在 O(log n) 时间内完成插入和删除，O(1) 时间内查询最大/最小值。
2. 空间效率高：使用数组存储，没有额外的指针开销。

劣势

1. 查找非极值元素慢：除了根节点，查找其他元素需要 O(n) 的时间。
2. 不适合静态数据：如果数据集是静态的，只需要找一次最大/最小值，那么直接遍历 O(n) 会更快。

适用场景

1. 优先队列：任何需要动态维护优先级并频繁提取最高优先级元素的场景，如任务调度、事件模拟。
2. 堆排序：一种 O(n log n) 的原地排序算法。
3. Top K 问题：在海量数据中找到最大或最小的 K 个元素。维护一个大小为 K 的最小堆（找 Top K 大）或最大堆（找 Top K 小）。
4. 中位数问题：使用一个最大堆和一个最小堆（对顶堆）来动态维护数据流的中位数。
5. 图论算法：Dijkstra 算法和 Prim 算法的堆优化版本。

总结

堆是一种看似简单但功能强大的数据结构。它通过维持“完全二叉树”的结构和“父节点总大于/小于子节点”的性质，巧妙地实现了在动态数据集中高效查找极值的功能。

本文核心要点

✅ 核心结构：逻辑上是完全二叉树，物理上用数组存储。
✅ 核心性质：最大堆（父 ≥ 子）或最小堆（父 ≤ 子）。
✅ 两大操作：sift_up（上浮，用于插入）和 sift_down（下沉，用于删除）。
✅ 复杂度：插入和删除为 O(log n)，查询极值为 O(1)，建堆为 O(n)。
✅ 核心应用：实现优先队列，解决 Top K、中位数、堆排序等问题。

掌握了堆，你就拥有了处理动态数据集合和优先级问题的利器。在下一篇文章中，我们将学习另一个非常有趣且实用的数据结构——并查集。