二叉堆详解：优先队列、代码与时间复杂度

堆解决什么问题

许多程序需要不断从一个变化的集合中取出最紧急的元素：模拟中的下一个事件、Dijkstra 算法中最近的未访问节点、优先级最高的任务，或数据流中最大的 k 个值。每次插入后都对整个集合排序，每次要花 O(n log n)。有序列表让移除变得便宜，但插入是 O(n)。堆让插入和移除最小值都是 O(log n)，这正是优先队列所需要的。

思路：把树存放在数组里

堆是一棵完全二叉树：除最后一层外每一层都是满的，最后一层从左到右填充。这样的形状让我们可以用一个普通列表存储这棵树，不需要任何指针。

两种修复操作用来维持堆性质。上浮：在末尾追加新元素后，只要它比父节点小，就与父节点交换。下沉：把最后一个元素移到根部后，只要它比较小的那个孩子大，就与该孩子交换。每个操作都沿着一条从根到叶子的路径移动，所以最多大约做 log2(n) 次交换。

示例演练：push 和 pop

从最小堆 [2, 5, 3, 9, 6] 开始（2 是根，它的孩子是 5 和 3，5 的孩子是 9 和 6）。

1. Push 1：把它追加到末尾，得到 [2, 5, 3, 9, 6, 1]。下标 5 的父节点是下标 2（值为 3）。
2. 1 比 3 小，交换：[2, 5, 1, 9, 6, 3]。现在下标 2 的父节点是下标 0（值为 2）。
3. 1 比 2 小，交换：[1, 5, 2, 9, 6, 3]。它到达了根部，停止。
4. Pop：移除根 1，把最后一个元素 3 移到根部：[3, 5, 2, 9, 6]。
5. 根的孩子是 5 和 2，较小的是 2，而 3 比它大，交换：[2, 5, 3, 9, 6]。下标 2 没有孩子，停止。这次 pop 返回了 1。

用 Python 实现最小堆

这个类演示了其中的机制。实际代码中请使用 heapq，见下一节。

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

用 Python heapq 实现优先队列

heapq 模块作用于普通列表，并始终把它维持为最小堆。heapify 能在 O(n) 时间内原地把现有列表变成堆。要使用优先级，就压入元组：Python 会逐个元素比较元组，所以第一个元素就是优先级。再加一个计数器作为决胜项，这样优先级相同的元素就不需要直接比较。

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

对于最大堆，Python 3.14 新增了 heapq.heapify_max、heapq.heappush_max 和 heapq.heappop_max。在旧版本中，常用的技巧是压入取负的键，例如 heapq.heappush(h, -score)，弹出时再取负。

时间与空间复杂度

调用 n 次 push 来建堆需要 O(n log n)。heapify 从最后一个父节点开始向根部逐个下沉，只需 O(n)，所以已经拿到全部元素时请优先使用它。

变体与常见错误

• 最大堆：代码相同，只是反转比较方向；在 Python 中，使用 _max 系列函数（3.14 及以上），或把键取负。
• d 叉堆：每个节点有 d 个孩子。树更矮，使 push 更便宜，pop 则稍贵一些。
• 带索引的优先队列 / decrease-key：heapq 无法原地修改某个元素的优先级。常见的变通办法（用于 Dijkstra 算法）是压入一个新条目，并在弹出过期条目时跳过它们。
• 比较不可比较的元素：压入 (priority, dict) 时，若两个优先级相等就会抛出 TypeError，因为 Python 接着会去比较字典。请把计数器作为元组的第二个元素。
• 把堆列表当作有序的。只有 heap[0] 有保证；如果需要全部有序，请使用 sorted(heap)。
• 把教科书中从 1 开始的公式（孩子为 2i 和 2i + 1）与从 0 开始的 Python 列表混用，造成差一错误。

何时使用堆，以及典型问题

当你不断只需要一个持续变化的集合中的最小或最大元素时，请使用堆。如果还需要有序遍历或任意删除，请使用有序列表或平衡树；如果只需要一次最小值，直接用 min() 即可。

经典用途：Dijkstra 最短路径和 Prim 最小生成树、合并 k 个有序列表（heapq.merge）、找出最大或最小的 k 个元素（维护一个大小为 k 的堆，O(n log k)）、滚动中位数（两个堆）、任务调度器和事件驱动的模拟，以及堆排序。