7.1 堆

前置：红黑树｜下一节：优先队列。这一页从完全二叉树的数组表示出发，依次实现上滤、下滤、Floyd 建堆和堆排序。

1. 完全二叉树如何落进数组

完全二叉树的最后一层从左向右填，所以按层编号后能连续存进数组。

索引：  0  1  2  3  4  5  6
数组：[1, 3, 2, 7, 6, 4, 5]

             1
          /     \
         3       2
       /  \    / \
      7    6   4   5

对零基索引 i：

• 当 i > 0 时，父节点是 (i - 1) // 2；根没有父节点；
• 左孩子是 2 * i + 1；
• 右孩子是 2 * i + 2。

最小堆要求父节点 <= 两个孩子，最大堆方向相反。请注意边界：不变量没有比较兄弟，也没有比较不同子树。根能确定为最小值；第二小的值只可能在根的孩子中，却不保证数组索引 1 就是第二小。查找任意值最坏仍是 O(n)。

2. 一份可检查的最小堆

新元素先放数组末尾，再与父节点比较；更小就向上换位，这叫上滤（sift up）。取走根以后，用末尾元素补根，再与两个孩子中更小者比较，必要时向下换位，这叫下滤（sift down）。

下面的泛型实现只调用 <，与 Python heapq一致。元素必须能按一致的顺序比较，排除 NaN 这类不满足顺序关系的值；入堆后也不能直接改比较字段。类型注解不会替你验证这个合同，比较抛错时本实现也不保证回滚。

from __future__ import annotations

from collections.abc import Iterable
from typing import Generic, TypeVar

T = TypeVar("T")

class MinHeap(Generic[T]):
    def __init__(self, values: Iterable[T] = ()) -> None:
        self._data = list(values)
        for i in range(len(self._data) // 2 - 1, -1, -1):
            self._sift_down(i)

    @classmethod
    def heapify(cls, values: Iterable[T]) -> "MinHeap[T]":
        return cls(values)

    def __len__(self) -> int:
        return len(self._data)

    def push(self, value: T) -> None:
        self._data.append(value)
        i = len(self._data) - 1
        while i > 0:
            parent = (i - 1) // 2
            if not self._data[i] < self._data[parent]:
                break
            self._data[parent], self._data[i] = self._data[i], self._data[parent]
            i = parent

    def peek(self) -> T:
        if not self._data:
            raise IndexError("peek from empty heap")
        return self._data[0]

    def pop(self) -> T:
        if not self._data:
            raise IndexError("pop from empty heap")
        root = self._data[0]
        last = self._data.pop()
        if self._data:
            self._data[0] = last
            self._sift_down(0)
        return root

    def _sift_down(self, i: int) -> None:
        n = len(self._data)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right
            if smallest == i:
                return
            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest

    def to_list(self) -> list[T]:
        return list(self._data)

    def is_valid(self) -> bool:
        n = len(self._data)
        for i in range(n // 2):
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and self._data[left] < self._data[i]:
                return False
            if right < n and self._data[right] < self._data[i]:
                return False
        return True

if __name__ == "__main__":
    heap = MinHeap([5, 3, 8, 1, 7])
    heap.push(0)
    assert heap.is_valid()
    print([heap.pop() for _ in range(len(heap))])

输出是 [0, 1, 3, 5, 7, 8]。数组中间状态可能与别人的实现不同，只要元素相同且父子不变量成立，就都是合法堆。

手推一次上滤

从 [1, 3, 2, 7, 6, 4, 5] 插入 0：

1. 0 先到索引 7，父节点索引为 3，值是 7；
2. 交换后到索引 3，父节点索引为 1，值是 3；
3. 再交换后到索引 1，父节点是根 1；
4. 最后交换，得到 [0, 1, 2, 3, 6, 4, 5, 7]。

上滤最多经过树高那么多层，因此堆调整为 O(log n)。本实现底层是 Python 列表：一次 append 扩容可能复制 O(n) 个引用，将扩容摊销后，插入才是 O(log(n+1))。

手推一次下滤

从 [0, 1, 2, 3, 6, 4, 5, 7] 取根：

1. 保存 0，末尾的 7 空降到根；
2. 根的孩子是 1 和 2，选更小的 1 交换；
3. 7 的新孩子是 3 和 6，选 3 交换；
4. 7 到叶子，得到 [1, 3, 2, 7, 6, 4, 5]。

peek 只读根，时间 O(1)；下滤最多走树高，调整成本为 O(log n)。CPython 的列表尾部 pop 也可能触发缩容，所以完整操作同样按摊销 O(log(n+1)) 计；单次扩缩容可能更贵。空堆检查为常数成本。

3. Floyd 建堆为什么是 O(n)

给定无序数组，不必逐个 push。Floyd 从最后一个内部节点 n // 2 - 1 开始，倒序对每个节点下滤。处理某节点时，它的两个子树已经是堆。

叶子占了约一半，移动 0 层；高度至少 1 的节点不超过 n/2，高度至少 2 的不超过 n/4。按“每个节点可能下降几层”计费：

总下降层数 <= floor(n/2) + floor(n/4) + ... + floor(n/2^floor(log2(n))) < n
(n >= 1)

这里求和只到树高，统计的是下降层数；每层比较和每个内部节点的固定工作仍要计入。Princeton 的分析给出线性的交换与比较上界。加上复制输入的 Θ(n)，本构造总时间为 Θ(n)。逐个插入则有 O(n log n) 上界。

构造器保存一份 Θ(n) 的浅拷贝，to_list() 也返回浅拷贝。修改原列表的槽位不会改堆，但列表中的可变对象仍被共享；改对象的排序字段会破坏不变量。is_valid() 扫描父子关系，时间 O(n)，辅助空间 O(1)。

4. 堆排序

升序原地堆排序要建最大堆。每轮把最大值从根换到当前区间末尾，再缩短区间并下滤根。

from typing import TypeVar

T = TypeVar("T")

def heap_sort(values: list[T]) -> list[T]:
    def sift_down(root: int, end: int) -> None:
        while True:
            largest = root
            left = 2 * root + 1
            right = 2 * root + 2
            if left < end and values[largest] < values[left]:
                largest = left
            if right < end and values[largest] < values[right]:
                largest = right
            if largest == root:
                return
            values[root], values[largest] = values[largest], values[root]
            root = largest

    n = len(values)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n)
    for end in range(n - 1, 0, -1):
        values[0], values[end] = values[end], values[0]
        sift_down(0, end)
    return values

if __name__ == "__main__":
    data = [4, 10, 3, 5, 1]
    print(heap_sort(data))

建堆是 O(n)，之后有 n - 1 次至多 O(log n) 的下滤，所以总时间 O(n log n)。函数修改传入列表，并返回同一个列表；示例输出 [1, 3, 4, 5, 10]。代码只用常数个额外变量，辅助空间 O(1)。远距离交换可能改变相等元素的先后次序，因此堆排序不稳定。

5. 调试清单

症状	先查哪里
pop 后根不是最小	下滤是否在左右孩子中选了更小者
偶数长度时越界	读取右孩子前是否检查 right < n
建堆漏掉根	倒序区间是否包含 0
调用者修改输入后堆也变	构造时是否复制输入，而非保存别名
打印数组看似无序	这通常正常；用 is_valid 检查父子关系
空堆返回含糊结果	peek 与 pop 是否统一抛出 IndexError

6. 何时不用堆

要查前驱、后继或任意范围，回到平衡 BST。要频繁按标识定位并修改任意节点，普通二叉堆没有索引表，查找仍是 O(n)。要完整有序输出，最终仍需反复 pop 或排序。

d-堆把每个节点的孩子数从 2 改成 d：树更矮，但下滤每层要比较更多孩子。实际快慢受数据规模、比较成本和内存布局影响，不能只凭树高断定四叉堆一定更快。

从堆结构到队列接口

上滤让末尾的新元素沿父链上升，下滤让根部的替身向较小孩子方向下降。Floyd 建堆仍然使用下滤，线性时间来自调度顺序：大量叶子无需移动，越靠近根、可能移动更远的节点越少。数组中间状态不必全局有序，父子不变量和根部极值才是合同。

下一节把这套结构封装成 优先队列，继续处理同优先级、任务取消与候选集合。