堆与优先队列

1. 概述与学习目标

1.1 什么是堆与优先队列

堆（Heap）是一种特殊的完全二叉树（Complete Binary Tree），满足堆序性质（Heap-Order Property）：

• 最大堆（Max-Heap）：每个节点的值 $\geq$ 其子节点的值，根节点存储最大值；
• 最小堆（Min-Heap）：每个节点的值 $\leq$ 其子节点的值，根节点存储最小值。

由于堆是完全二叉树，可以用数组紧凑存储无需指针，索引 $i$ 的父节点为 $\lfloor (i-1)/2 \rfloor$，左子节点为 $2i+1$，右子节点为 $2i+2$。这一性质由 Williams 1964 年在《Communications of the ACM》Algorithm 232: Heapsort 中首次系统化定义，至今仍是工业级优先队列的首选实现。

优先队列（Priority Queue, PQ）是一种抽象数据类型（ADT），每次出队的元素是优先级最高（或最低）的元素。堆是优先队列最常用的底层实现，但优先队列也可用有序数组、平衡树、跳表等结构实现。

最大堆 (Max-Heap):                  最小堆 (Min-Heap):
        9                                   1
       / \                                 / \
      8   7                               2   3
     / \ / \                             / \ / \
    5  6 4  3                           6  5 4  7

数组表示 (0-based):
索引:  0  1  2  3  4  5  6
最大堆: 9  8  7  5  6  4  3
最小堆: 1  2  3  6  5  4  7

一句话定义：堆 = 完全二叉树 + 堆序性质 + 数组紧凑存储，插入/删除 $O(\log n)$，建堆 $O(n)$，查看极值 $O(1)$；优先队列 = 抽象 ADT，堆是其工业级首选实现，从 Dijkstra 到定时器调度均不可替代。

1.2 学习目标

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

1. 记忆堆作为完全二叉树数组表示的形式化定义 $\text{parent}(i) = \lfloor (i-1)/2 \rfloor$、$\text{left}(i) = 2i+1$、$\text{right}(i) = 2i+2$，复述最大堆/最小堆在插入、删除堆顶、查看堆顶、建堆操作上的时间复杂度差异；
2. 理解 Williams 1964《Algorithm 232: Heapsort》首次提出堆与堆排序、Floyd 1964《Algorithm 245: Treesort》改进建堆至 $O(n)$、Vuillemin 1978 二项堆、Fredman-Tarjan 1984 Fibonacci 堆（JACM 34(3):596-615）的历史脉络，说明堆为何在优先级调度场景下不可替代；
3. 应用二叉堆的上浮（sift-up）、下沉（sift-down）、Floyd 自底向上建堆、堆排序、Top-K、索引堆编写可运行的 Python/C++/Java 代码，解决 LeetCode 215 第 K 大、LeetCode 23 合并 K 个有序链表、LeetCode 295 数据流中位数、LeetCode 621 任务调度器等问题；
4. 分析 Floyd 建堆 $O(n)$ 复杂度的数学证明 $\sum_{h=0}^{\lfloor \log n \rfloor} \lceil n/2^{h+1} \rceil \cdot h \leq 2n$、堆排序 $O(n \log n)$ 最坏复杂度、Fibonacci 堆的均摊分析，掌握”层高加权节点数求和”核心论证方法；
5. 评估二叉堆相对于有序数组、平衡树、跳表、Fibonacci 堆在”插入-删除极值”问题维度上的优劣，识别 Dijkstra 算法、Prim 算法、Huffman 编码、定时器调度、操作系统任务调度中的选型动机；
6. 对比二叉堆、d-ary 堆、二项堆、Fibonacci 堆、配对堆、左偏堆、索引堆在插入、删除极值、合并、减小键值、均摊复杂度、实现复杂度维度的差异；
7. 创造性设计基于堆的开源项目解决方案，如定时器轮、限流器、Top-K 流式聚合、A* 搜索优先队列、Huffman 编码器、Redis Stream 排序、Linux kernel timer wheel。

1.3 术语表

1.4 堆 vs 其他优先队列实现

1.5 适用场景与不适用场景

跨模块引用：堆作为完全二叉树的应用参见 树；堆排序与快排、归并的对比参见 排序算法；Dijkstra/Prim 算法中堆的应用参见 图算法；堆在流式数据 Top-K 中的应用参见 查找算法；堆作为优先队列与栈/队列的对比参见 栈与队列。

2. 历史动机与演进

2.1 前堆时代：选择排序的困境

1960 年代初期，计算机科学刚刚成形，排序是核心问题之一。已知的高效排序算法有：

• 快速排序（Hoare 1959）：平均 $O(n \log n)$，最坏 $O(n^2)$；
• 归并排序（von Neumann 1945）：$O(n \log n)$，但需要 $O(n)$ 额外空间；
• 选择排序（朴素）：$O(n^2)$，但仅需 $O(1)$ 原地空间。

工业场景迫切需要一种最坏 $O(n \log n)$ + 原地的排序算法。这一需求推动了堆与堆排序的诞生。

2.2 Williams 1964：Algorithm 232 Heapsort

1964 年 6 月，英国 Elliott Brothers 公司的 J. W. J. Williams 在 Communications of the ACM 7(6): 347-348 发表短论文《Algorithm 232: Heapsort》，首次提出堆数据结构与堆排序算法：

• 定义”堆”为满足堆序性质的完全二叉树；
• 提出上浮（sift-up）操作用于插入；
• 提出堆排序算法：先逐个插入建堆 $O(n \log n)$，再逐个删除堆顶 $O(n \log n)$；
• 总体最坏复杂度 $O(n \log n)$ + 原地 $O(1)$ 空间。

Williams 的论文极为简洁（仅 2 页），但开创了完全二叉树数组表示与堆序性质的研究方向。该论文引用量超 1500 次，是计算机科学史上最具影响力的短论文之一。

2.3 Floyd 1964：Algorithm 245 Treesort3

Williams 的堆排序有一个缺陷：建堆阶段是逐个插入，复杂度 $O(n \log n)$。Robert W. Floyd（斯坦福大学，1978 年 ACM Turing Award 得主）在同年的 Communications of the ACM 7(12): 701 发表《Algorithm 245: Treesort 3》，提出自底向上建堆法（后称 Floyd 建堆法）：

• 将所有元素放入数组；
• 从最后一个非叶子节点开始，依次执行下沉操作；
• 建堆复杂度降至 $O(n)$。

Floyd 的改进使堆排序的整体复杂度仍为 $O(n \log n)$（瓶颈在删除阶段），但建堆阶段从 $O(n \log n)$ 降至 $O(n)$，常数更优。该算法后来被 CLRS 第 6.3 节作为标准建堆方法讲授。

教学提示：Floyd 是计算机科学全才，除堆排序外还贡献了 Floyd-Warshall 全源最短路径算法（1962）、Floyd-Hoare 程序验证逻辑（1967）、ALGOL 60 编译器（1963）等。1978 年获 ACM Turing Award，颁奖词强调”for having a clear influence on methodologies for the creation of efficient and reliable software”。

2.4 Knuth 1968：TAOCP Vol.1 系统化理论

1968 年，Donald E. Knuth 出版《The Art of Computer Programming, Volume 1: Fundamental Algorithms》，在 Section 5.2.3（Sorting by Selection）系统化堆与堆排序理论：

• 形式化定义完全二叉树、堆序性质；
• 给出 0-based 与 1-based 索引公式；
• 详细推导 Floyd 建堆 $O(n)$ 的数学证明；
• 讨论堆在优先队列、选择问题中的应用。

TAOCP Vol.1 成为堆教学的金标准，后续教材（CLRS、Sedgewick、Mark Allen Weiss）均沿用其框架。

2.5 Vuillemin 1978：二项堆

1978 年 4 月，法国数学家 Jean Vuillemin 在 Communications of the ACM 21(4): 309-315 发表《A data structure for manipulating priority queues》，提出二项堆（Binomial Heap）：

• 由多棵二项树（Binomial Tree）组成的森林；
• 二项树 $B_k$ 递归定义：$B_0$ 为单节点，$B_k$ 由两棵 $B_{k-1}$ 合并而成（一棵作为另一棵的左子树）；
• $B_k$ 有 $2^k$ 个节点，高度为 $k$；
• 二项堆支持 $O(\log n)$ 合并（union），远优于二叉堆的 $O(n)$ 合并。

二项堆是第一个支持高效合并的优先队列实现，奠定了可合并堆（Mergeable Heap）的研究方向。

2.6 Fredman-Tarjan 1984：Fibonacci 堆

1984 年，AT&T Bell Labs 的 Michael L. Fredman 与 Robert Endre Tarjan 在 Journal of the ACM 34(3): 596-615 发表《Fibonacci heaps and their uses in improved network optimization algorithms》（论文实际投稿 1984，正式发表 1987），提出 Fibonacci 堆：

• 基于二项堆，引入懒惰合并（lazy union）策略；
• 插入 $O(1)$ 均摊，decrease-key $O(1)$ 均摊，删除极值 $O(\log n)$ 均摊；
• 节点度数上界用 Fibonacci 数列证明：度数为 $k$ 的节点至少有 $F_{k+2}$ 个后代，故 $k \leq \log_\phi n$（$\phi = (1+\sqrt{5})/2 \approx 1.618$ 为黄金比）。

Fibonacci 堆将 Dijkstra 算法的时间复杂度从 $O((V+E) \log V)$ 优化到 $O(E + V \log V)$，在稀疏图上提升显著。Tarjan 因此获 1986 年 ACM Turing Award。

工程现实：尽管 Fibonacci 堆在理论上更优，但其实现复杂、常数大，工业实践中通常仍用二叉堆或配对堆。CLRS 第 19 章用整整一章讲解 Fibonacci 堆，但作者承认”for most practical purposes, a binary heap is faster”。

2.7 Fredman-Sedgewick-Sleator-Tarjan 1986：配对堆

1986 年，Fredman、Sedgewick、Sleator、Tarjan 在 Algorithmica 1(1): 111-129 发表《The pairing heap: a new form of self-adjusting heap》，提出配对堆（Pairing Heap）：

• 基于自调整（self-adjusting）思想，类似 Sleator-Tarjan 1985 的 Splay 树；
• 实现简单（仅 100 行 C 代码），均摊性能接近 Fibonacci 堆；
• delete-min 操作的核心是”两两配对合并”：将根的所有子树两两合并，再合并剩余子树；
• decrease-key 的均摊复杂度仍是开放问题，已知上界 $o(\log n)$，但下界证明 Fibonacci 堆更优。

配对堆因其实现简单 + 性能优秀，成为 GNU C++ 标准库 __gnu_cxx::priority_queue 与 Linux kernel 的可选优先队列实现。

2.8 Linux kernel 1991：定时器堆

1991 年 Linus Torvalds 创建 Linux kernel，定时器（timer）是核心子系统之一。Linux 定时器实现经历了三个阶段：

1. timer wheel（1991-2016）：基于哈希 + 链表的近似定时器，按到期时间分桶，复杂度 $O(1)$ 插入但精度低；
2. red-black tree timer（2016-）：内核 4.8 后改用红黑树（rbtree），按到期时间排序，$O(\log n)$ 插入删除；
3. hrtimer（high-resolution timer）：高精度定时器，底层也是红黑树。

虽然 Linux 未直接使用堆，但红黑树与堆在优先队列语义上等价，都是 $O(\log n)$ 插入删除极值。

2.9 Go 2009：container/heap 包

2009 年 Go 语言发布，标准库 container/heap 提供通用堆接口：

type Interface interface {
    sort.Interface
    Push(x any) // add x as element Len()
    Pop() any   // remove and return element Len() - 1
}

用户实现 Interface 即可获得最小堆。最大堆通过 Less 反向比较实现。Go 的 timer 与 runtime netpoller 均基于四叉堆（quaternary heap，d=4）实现，平衡了树高与节点度数。

2.10 演进时间线

timeline
    title 堆与优先队列演进时间线
    1964 : Williams Algorithm 232 Heapsort (CACM 7:347-348)
    1964 : Floyd Algorithm 245 Treesort3 改进建堆 O(n) (CACM 7:701)
    1968 : Knuth TAOCP Vol.1 §5.2.3 系统化理论
    1972 : Crane 左偏堆 (Stanford STAN-CS-72-259)
    1975 : Tarjan 二项堆复杂度分析
    1978 : Vuillemin 二项堆 (CACM 21:309-315)
    1984 : Fredman-Tarjan Fibonacci 堆 (JACM 投稿)
    1986 : Fredman-Sedgewick-Sleator-Tarjan 配对堆 (Algorithmica 1:111-129)
    1986 : Tarjan 获 ACM Turing Award
    1991 : Linux kernel timer wheel
    1995 : Java 1.0 java.util.PriorityQueue
    2002 : C++ STL std::priority_queue (C++98)
    2009 : Go container/heap 标准库
    2016 : Linux kernel 4.8 hrtimer 改用 rbtree

3. 形式化定义

3.1 完全二叉树的数学定义

完全二叉树（Complete Binary Tree）是满足以下性质的二叉树：

1. 除最后一层外，所有层都”满”（节点数达最大值 $2^l$，$l$ 为层号从 0 开始）；
2. 最后一层的节点从左向右紧凑排列，中间无空缺。

形式化定义：设二叉树有 $n$ 个节点，按层序从上到下、从左到右编号 $0, 1, \ldots, n-1$。若对任意节点 $i$：

• 左子节点存在当且仅当 $2i+1 < n$；
• 右子节点存在当且仅当 $2i+2 < n$；
• 父节点存在当且仅当 $i > 0$，且为 $\lfloor (i-1)/2 \rfloor$；

则该二叉树为完全二叉树。

高度：$n$ 个节点的完全二叉树高度 $h = \lfloor \log_2 n \rfloor$。

3.2 堆序性质的形式化定义

设堆 $H$ 是存储 $n$ 个元素的完全二叉树，节点 $i$ 存储键值 $H[i]$。堆满足：

• 最大堆性质：对所有 $i > 0$，$H[\text{parent}(i)] \geq H[i]$；
• 最小堆性质：对所有 $i > 0$，$H[\text{parent}(i)] \leq H[i]$。

其中 $\text{parent}(i) = \lfloor (i-1)/2 \rfloor$（0-based）或 $\lfloor i/2 \rfloor$（1-based）。

推论（最大堆）：

1. 根节点 $H[0]$ 是最大值；
2. 任意子树仍是最大堆；
3. 任意从根到叶子的路径是非递增序列；
4. 第 $k$ 大元素必在前 $k$ 层（但前 $k$ 层未必按序）。

3.3 索引公式的推导

0-based 索引（C/C++/Java/Python 默认）：

1-based 索引（CLRS 默认、Fortran）：

教学提示：1-based 索引的公式更简洁（无 $+1$ $-1$），故 CLRS 全书采用 1-based。但 C/C++/Java/Python 数组从 0 开始，工程实现需要做转换。Sedgewick《Algorithms》第 4 版采用 0-based 并接受公式稍繁琐的代价。

3.4 优先队列 ADT

优先队列（Priority Queue）的抽象数据类型定义为：

ADT Priority Queue {
  数据：n 个元素，每个元素关联一个可比较的优先级键
  操作：
    insert(x)        // 插入元素 x，O(log n)
    findMin()/findMax()  // 返回极值，O(1)
    deleteMin()/deleteMax()  // 删除并返回极值，O(log n)
    isEmpty()        // 判断是否为空，O(1)
    size()           // 返回元素数，O(1)
    // 可选：
    union(PQ Q)      // 合并另一优先队列
    decreaseKey(x, k)  // 减小元素 x 的键值
    delete(x)        // 删除任意元素 x
}

堆是该 ADT 的最常用实现，但实现不唯一。

4. 二叉堆的实现

4.1 上浮操作（Sift-Up / Swim）

场景：在堆尾插入新元素后，将其向上调整以恢复堆序性质。

算法（最大堆）：

1. 将新元素放在数组末尾位置 $i$；
2. 比较 $H[i]$ 与 $H[\text{parent}(i)]$：
   • 若 $H[i] > H[\text{parent}(i)]$，交换；
   • 否则停止；
3. 重复步骤 2，直到 $i = 0$ 或停止条件满足。

示例（向最大堆插入 9）：

初始: [8, 5, 7, 3, 4, 6, 9]  ← 9 在末尾 (i=6)
  parent(6) = (6-1)/2 = 2，H[2]=7 < 9 → 交换
        [8, 5, 9, 3, 4, 6, 7]  ← i=2
  parent(2) = (2-1)/2 = 0，H[0]=8 < 9 → 交换
        [9, 5, 8, 3, 4, 6, 7]  ← i=0，完成

Python 实现：

def sift_up(heap: list[int], i: int) -> None:
    """最大堆的上浮操作（0-based）。"""
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] <= heap[parent]:
            break
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

C++ 实现：

// 最大堆的上浮操作（0-based）
void siftUp(std::vector<int>& heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] <= heap[parent]) break;
        std::swap(heap[i], heap[parent]);
        i = parent;
    }
}

Java 实现：

// 最大堆的上浮操作（0-based）
private void siftUp(int[] heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] <= heap[parent]) break;
        int tmp = heap[i];
        heap[i] = heap[parent];
        heap[parent] = tmp;
        i = parent;
    }
}

复杂度：

• 时间：$O(\log n)$（最坏从叶子上浮到根，路径长度为树高 $\lfloor \log_2 n \rfloor$）；
• 空间：$O(1)$（迭代实现，无递归栈）。

4.2 下沉操作（Sift-Down / Sink）

场景：删除堆顶后，将末尾元素补到堆顶，向下调整以恢复堆序性质。

算法（最大堆）：

1. 将末尾元素移到堆顶位置 $i = 0$；
2. 比较 $H[i]$ 与 $H[\text{left}(i)]$、$H[\text{right}(i)]$，找出较大者 $H[\text{largest}]$：
   • 若 $H[\text{largest}] > H[i]$，交换 $H[i]$ 与 $H[\text{largest}]$；
   • 否则停止；
3. 重复步骤 2，直到 $i$ 为叶子或停止条件满足。

示例（删除最大堆堆顶 9）：

初始: [9, 5, 8, 3, 4, 6, 7]
  末尾 7 移到堆顶: [7, 5, 8, 3, 4, 6]  ← size=6
  i=0，left=1 (5)，right=2 (8)，largest=2 → 交换
        [8, 5, 7, 3, 4, 6]  ← i=2
  i=2，left=5 (6)，right=6 (越界)，largest=5 → 交换
        [8, 5, 6, 3, 4, 7]  ← i=5，叶子，完成

Python 实现：

def sift_down(heap: list[int], i: int, size: int) -> None:
    """最大堆的下沉操作（0-based）。"""
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < size and heap[left] > heap[largest]:
            largest = left
        if right < size and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest

C++ 实现：

void siftDown(std::vector<int>& heap, int i, int size) {
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < size && heap[left] > heap[largest]) largest = left;
        if (right < size && heap[right] > heap[largest]) largest = right;
        if (largest == i) break;
        std::swap(heap[i], heap[largest]);
        i = largest;
    }
}

Java 实现：

private void siftDown(int[] heap, int i, int size) {
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < size && heap[left] > heap[largest]) largest = left;
        if (right < size && heap[right] > heap[largest]) largest = right;
        if (largest == i) break;
        int tmp = heap[i]; heap[i] = heap[largest]; heap[largest] = tmp;
        i = largest;
    }
}

复杂度：

• 时间：$O(\log n)$（最坏从根下沉到叶子）；
• 空间：$O(1)$。

4.3 完整的最大堆实现

Python 实现（含容量管理）：

from typing import Generic, TypeVar

T = TypeVar('T')


class MaxHeap(Generic[T]):
    """最大堆的完整实现，基于动态数组。"""

    def __init__(self, capacity: int = 10) -> None:
        self._data: list[T | None] = [None] * capacity
        self._size = 0
        self._capacity = capacity

    def push(self, value: T) -> None:
        """插入元素，O(log n)。"""
        if self._size == self._capacity:
            self._resize(self._capacity * 2)
        self._data[self._size] = value
        self._sift_up(self._size)
        self._size += 1

    def pop(self) -> T:
        """删除并返回堆顶（最大值），O(log n)。"""
        if self._size == 0:
            raise IndexError("pop from empty heap")
        top = self._data[0]
        self._size -= 1
        self._data[0] = self._data[self._size]
        self._data[self._size] = None  # 帮助 GC
        if self._size > 0:
            self._sift_down(0)
        return top  # type: ignore[return-value]

    def peek(self) -> T:
        """返回堆顶，O(1)。"""
        if self._size == 0:
            raise IndexError("peek from empty heap")
        return self._data[0]  # type: ignore[return-value]

    def __len__(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def _resize(self, new_cap: int) -> None:
        old = self._data
        self._data = [None] * new_cap
        for i in range(self._size):
            self._data[i] = old[i]
        self._capacity = new_cap

    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self._data[i] <= self._data[parent]:  # type: ignore[operator]
                break
            self._data[i], self._data[parent] = self._data[parent], self._data[i]
            i = parent

    def _sift_down(self, i: int) -> None:
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            largest = i
            if left < self._size and self._data[left] > self._data[largest]:  # type: ignore[operator]
                largest = left
            if right < self._size and self._data[right] > self._data[largest]:  # type: ignore[operator]
                largest = right
            if largest == i:
                break
            self._data[i], self._data[largest] = self._data[largest], self._data[i]
            i = largest

C++ 实现（模板类，支持任意可比较类型）：

#include <vector>
#include <algorithm>
#include <stdexcept>

template <typename T>
class MaxHeap {
private:
    std::vector<T> data_;

    void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (data_[i] <= data_[parent]) break;
            std::swap(data_[i], data_[parent]);
            i = parent;
        }
    }

    void siftDown(int i) {
        int n = static_cast<int>(data_.size());
        while (true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;
            if (left < n && data_[left] > data_[largest]) largest = left;
            if (right < n && data_[right] > data_[largest]) largest = right;
            if (largest == i) break;
            std::swap(data_[i], data_[largest]);
            i = largest;
        }
    }

public:
    void push(const T& value) {
        data_.push_back(value);
        siftUp(static_cast<int>(data_.size()) - 1);
    }

    T pop() {
        if (data_.empty()) throw std::runtime_error("pop from empty heap");
        T top = data_[0];
        data_[0] = data_.back();
        data_.pop_back();
        if (!data_.empty()) siftDown(0);
        return top;
    }

    const T& top() const {
        if (data_.empty()) throw std::runtime_error("top from empty heap");
        return data_[0];
    }

    bool empty() const { return data_.empty(); }
    size_t size() const { return data_.size(); }
};

Java 实现（泛型，支持自定义比较器）：

import java.util.Comparator;
import java.util.Arrays;

public class MaxHeap<T> {
    private Object[] data;
    private int size;
    private final Comparator<? super T> comparator;

    @SuppressWarnings("unchecked")
    public MaxHeap(int capacity, Comparator<? super T> comparator) {
        this.data = new Object[capacity];
        this.size = 0;
        this.comparator = comparator;
    }

    public MaxHeap(int capacity) {
        this(capacity, (a, b) -> ((Comparable<T>) a).compareTo(b));
    }

    @SuppressWarnings("unchecked")
    public void push(T value) {
        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);
        data[size] = value;
        siftUp(size);
        size++;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (size == 0) throw new RuntimeException("pop from empty heap");
        T top = (T) data[0];
        size--;
        data[0] = data[size];
        data[size] = null;
        if (size > 0) siftDown(0);
        return top;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (size == 0) throw new RuntimeException("peek from empty heap");
        return (T) data[0];
    }

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    @SuppressWarnings("unchecked")
    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (comparator.compare((T) data[i], (T) data[parent]) <= 0) break;
            Object tmp = data[i]; data[i] = data[parent]; data[parent] = tmp;
            i = parent;
        }
    }

    @SuppressWarnings("unchecked")
    private void siftDown(int i) {
        while (true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;
            if (left < size && comparator.compare((T) data[left], (T) data[largest]) > 0)
                largest = left;
            if (right < size && comparator.compare((T) data[right], (T) data[largest]) > 0)
                largest = right;
            if (largest == i) break;
            Object tmp = data[i]; data[i] = data[largest]; data[largest] = tmp;
            i = largest;
        }
    }
}

4.4 三语言实现对比

5. 建堆操作与 $O(n)$ 证明

5.1 自顶向下建堆（逐个插入）

将 $n$ 个元素逐个插入空堆，每次插入后上浮：

def build_heap_top_down(arr: list[int]) -> list[int]:
    """自顶向下建堆，O(n log n)。"""
    heap: list[int] = []
    for x in arr:
        heap.append(x)
        sift_up(heap, len(heap) - 1)
    return heap

复杂度：第 $i$ 次插入的代价为 $O(\log i)$，总复杂度：

$T(n) = \sum_{i=1}^{n} O(\log i) = O(n \log n)$

5.2 Floyd 自底向上建堆（$O(n)$）

Floyd 建堆法（Floyd’s Build-Heap）：将所有元素放入数组，从最后一个非叶子节点开始，依次执行下沉操作。

def build_heap_floyd(arr: list[int]) -> list[int]:
    """Floyd 自底向上建堆，O(n)。"""
    n = len(arr)
    # 从最后一个非叶子节点开始（索引 (n//2) - 1），向前依次下沉
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

C++ 实现：

void buildHeapFloyd(std::vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(arr, i, n);
    }
}

示例（建最大堆，arr = [3, 1, 4, 1, 5, 9, 2, 6]）：

初始: [3, 1, 4, 1, 5, 9, 2, 6]，n=8
最后一个非叶子: i = 8//2 - 1 = 3

i=3: siftDown(3) → [3, 1, 4, 6, 5, 9, 2, 1]  (1<6 交换)
i=2: siftDown(2) → [3, 1, 9, 6, 5, 4, 2, 1]  (4<9 交换)
i=1: siftDown(1) → [3, 6, 9, 1, 5, 4, 2, 1]  (1<6 交换)
                  → [3, 6, 9, 1, 5, 4, 2, 1]  (1<5 不交换，停止)
i=0: siftDown(0) → [9, 6, 3, 1, 5, 4, 2, 1]  (3<9 交换)
                  → [9, 6, 4, 1, 5, 3, 2, 1]  (3<4 交换)
                  → [9, 6, 4, 1, 5, 3, 2, 1]  (3 是叶子，停止)

最终最大堆: [9, 6, 4, 1, 5, 3, 2, 1]

5.3 建堆 $O(n)$ 的数学证明

定理：用 Floyd 建堆法在 $n$ 个元素上建堆的时间复杂度为 $O(n)$。

证明（基于层高加权节点数求和）：

设堆高度为 $h = \lfloor \log_2 n \rfloor$。在第 $l$ 层（从根 0 开始）有 $\lceil n/2^{l+1} \rceil$ 个节点（至多 $2^l$ 个），每个节点至多下沉 $h - l$ 次。

总工作量为：

$T(n) = \sum_{l=0}^{h} \lceil n/2^{l+1} \rceil \cdot (h - l)$

令 $k = h - l$，则 $l = h - k$，$k$ 从 $0$ 到 $h$：

$T(n) = \sum_{k=0}^{h} \lceil n/2^{h-k+1} \rceil \cdot k$

注意到 $\lceil n/2^{h-k+1} \rceil \leq n/2^{h-k+1} + 1 \leq 2 \cdot n/2^{h-k+1} = n/2^{h-k}$（对 $k \geq 1$），故：

$T(n) \leq \sum_{k=0}^{h} \frac{n}{2^{h-k}} \cdot k = n \sum_{k=0}^{h} \frac{k}{2^{h-k}}$

令 $j = h - k$，则 $k = h - j$，$j$ 从 $0$ 到 $h$：

$T(n) \leq n \sum_{j=0}^{h} \frac{h - j}{2^j} = n \left( h \sum_{j=0}^{h} \frac{1}{2^j} - \sum_{j=0}^{h} \frac{j}{2^j} \right)$

利用两个无穷级数和：

• $\sum_{j=0}^{\infty} \frac{1}{2^j} = 2$（几何级数）；
• $\sum_{j=0}^{\infty} \frac{j}{2^j} = 2$（标准结果，对 $\sum j x^j = x/(1-x)^2$ 在 $x = 1/2$ 求值）。

故：

$T(n) \leq n (2h - 2) = 2n \log_2 n - 2n$

等等，这与 $O(n)$ 矛盾。哪里出错了？

修正：上面推导有误。正确做法是用每层节点数的精确上界 $\lceil n/2^{l+1} \rceil \leq n/2^{l+1} + 1$，但更精细的分析应考虑：

• 高度为 $h$ 的节点：1 个（根），下沉至多 $h$ 次；
• 高度为 $h-1$ 的节点：2 个，下沉至多 $h-1$ 次；
• …
• 高度为 0 的节点：$\approx n/2$ 个，下沉 0 次。

关键观察：高度为 $k$ 的节点至多有 $\lceil n/2^{k+1} \rceil$ 个，每个下沉至多 $k$ 次。

$T(n) = \sum_{k=0}^{h} \left\lceil \frac{n}{2^{k+1}} \right\rceil \cdot k \leq \sum_{k=0}^{h} \frac{n}{2^k} \cdot k = n \sum_{k=0}^{h} \frac{k}{2^k}$

利用 $\sum_{k=0}^{\infty} \frac{k}{2^k} = 2$（标准结果），故：

$T(n) \leq n \cdot 2 = 2n = O(n) \qquad \blacksquare$

直观理解：

总工作量 $\approx \sum_{k=1}^{h} 2^{h-k} \cdot k = 2^h \sum_{k=1}^{h} k/2^k \leq 2^h \cdot 2 = 2n$。

关键洞见：大部分节点在底层，下沉距离短；少数节点在高层，下沉距离长。两者相互抵消，总工作量为 $O(n)$。

6. 堆排序

6.1 算法

堆排序（Heapsort）利用最大堆的性质，每次取出堆顶（最大值）放到数组末尾：

1. 建堆阶段：用 Floyd 建堆法将数组构造为最大堆，$O(n)$；
2. 排序阶段：循环 $n-1$ 次：
   • 将堆顶 arr[0] 与末尾 arr[i] 交换；
   • 堆大小减一（size = i）；
   • 对堆顶执行下沉操作恢复堆序性质，$O(\log n)$；
3. 总复杂度：$O(n) + (n-1) \cdot O(\log n) = O(n \log n)$。

6.2 Python 实现

def heap_sort(arr: list[int]) -> list[int]:
    """堆排序（原地，升序），O(n log n)。"""
    n = len(arr)

    # 1. 建最大堆（Floyd 法），O(n)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i, n)

    # 2. 逐个提取最大值放到末尾，O(n log n)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 堆顶与末尾交换
        _sift_down(arr, 0, i)  # 对剩余元素下沉

    return arr


def _sift_down(heap: list[int], i: int, size: int) -> None:
    """最大堆的下沉操作。"""
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < size and heap[left] > heap[largest]:
            largest = left
        if right < size and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest

6.3 C++ 实现

#include <vector>

void siftDown(std::vector<int>& arr, int i, int size) {
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < size && arr[left] > arr[largest]) largest = left;
        if (right < size && arr[right] > arr[largest]) largest = right;
        if (largest == i) break;
        std::swap(arr[i], arr[largest]);
        i = largest;
    }
}

void heapSort(std::vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    // 1. 建最大堆
    for (int i = n / 2 - 1; i >= 0; --i) siftDown(arr, i, n);
    // 2. 逐个提取
    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        siftDown(arr, 0, i);
    }
}

6.4 Java 实现

public static void heapSort(int[] arr) {
    int n = arr.length;
    // 1. 建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);
    // 2. 逐个提取
    for (int i = n - 1; i > 0; i--) {
        int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
        siftDown(arr, 0, i);
    }
}

private static void siftDown(int[] arr, int i, int size) {
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if (left < size && arr[left] > arr[largest]) largest = left;
        if (right < size && arr[right] > arr[largest]) largest = right;
        if (largest == i) break;
        int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
        i = largest;
    }
}

6.5 堆排序特性

为什么不稳定？

堆排序的交换是 arr[0] 与 arr[i] 的长距离交换，可能改变相等元素的相对顺序。

示例：考虑序列 [5a, 5b, 5c]（5a、5b、5c 键值相同），建堆后可能为 [5a, 5b, 5c]，排序后可能变为 [5c, 5b, 5a]，相对顺序被破坏。

与快排、归并的对比：

堆排序的最大优势是最坏 $O(n \log n)$ + 原地 $O(1)$，但其常数大、缓存不友好，实际速度通常慢于快排。Java 的 Arrays.sort(int[]) 在小规模用快排（双轴），大规模用归并；堆排序通常只在需要”最坏保证 + 原地”时使用（如嵌入式系统、实时系统）。

7. 优先队列 ADT 与多语言实现

7.1 优先队列的接口

from abc import ABC, abstractmethod
from typing import Generic, TypeVar

T = TypeVar('T')


class PriorityQueue(ABC, Generic[T]):
    """优先队列抽象数据类型。"""

    @abstractmethod
    def push(self, value: T) -> None: ...

    @abstractmethod
    def pop(self) -> T: ...

    @abstractmethod
    def peek(self) -> T: ...

    @abstractmethod
    def __len__(self) -> int: ...

7.2 Python heapq 模块

Python 标准库 heapq 提供最小堆操作：

import heapq

# 基本操作
heap: list[int] = []
heapq.heappush(heap, 5)  # O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappop(heap)  # 返回 1，O(log n)
heapq.heappushpop(heap, 2)  # 先 push 再 pop，比分别调用更高效
heapq.heapreplace(heap, 4)  # 先 pop 再 push

# 建堆
arr = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(arr)  # O(n) Floyd 建堆

# Top-K
largest = heapq.nlargest(3, arr)  # [9, 6, 5]
smallest = heapq.nsmallest(3, arr)  # [1, 1, 2]

# 最大堆技巧：取负数
max_heap: list[int] = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -3)
heapq.heappop(max_heap)  # 返回 -5，即原值 5

# 复合元素（按元组第一元素排序）
pq: list[tuple[int, str]] = []
heapq.heappush(pq, (3, "low priority"))
heapq.heappush(pq, (1, "high priority"))
heapq.heappush(pq, (2, "medium priority"))
heapq.heappop(pq)  # (1, "high priority")

CPython heapq 实现（简化版）：

# CPython Lib/heapq.py 核心实现（简化）
def heappush(heap, item):
    heap.append(item)
    _siftdown(heap, 0, len(heap) - 1)

def heappop(heap):
    lastelt = heap.pop()
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
    else:
        returnitem = lastelt
    return returnitem

def _siftdown(heap, startpos, pos):
    """将 pos 处元素向上调整（CPython 命名：siftdown = 上浮）。"""
    newitem = heap[pos]
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

def _siftup(heap, pos):
    """将 pos 处元素向下调整（CPython 命名：siftup = 下沉）。"""
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    childpos = 2 * pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2 * pos + 1
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

命名陷阱：CPython 的 _siftdown 实际是”上浮”，_siftup 实际是”下沉”。命名源自元素在数组中”向下移动到根”或”向上移动到叶”，与 Sedgewick/CLRS 的命名相反。这是历史遗留命名，使用时需注意。

7.3 C++ std::priority_queue

C++ STL 的 std::priority_queue 默认是最大堆：

#include <queue>
#include <vector>
#include <functional>  // std::greater

// 最大堆（默认）
std::priority_queue<int> maxHeap;
maxHeap.push(5);
maxHeap.push(1);
maxHeap.push(3);
maxHeap.top();  // 5
maxHeap.pop();

// 最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(5);
minHeap.push(1);
minHeap.push(3);
minHeap.top();  // 1

// 自定义比较器（按 pair 第二元素）
auto cmp = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second > b.second;  // 最小堆
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> pq(cmp);

C++ priority_queue 的局限：

• 不支持随机访问，无法 pq[i]；
• 不支持删除任意元素（无 erase）；
• 不支持 decrease-key；
• 底层容器默认 std::vector，可用 std::deque。

替代方案：boost::heap::priority_queue、__gnu_cxx::priority_queue（配对堆）支持更多操作。

7.4 Java PriorityQueue

Java 的 java.util.PriorityQueue 默认是最小堆：

import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Comparator;

// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.poll();  // 1

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.poll();  // 5

// 自定义比较器
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{3, "task3"});
pq.offer(new int[]{1, "task1"});
pq.poll();  // {1, "task1"}

// 初始容量 + 比较器
PriorityQueue<String> strPq = new PriorityQueue<>(100, Comparator.comparingInt(String::length));

Java PriorityQueue 的特性：

• 基于动态数组（默认容量 11）；
• 不是线程安全的，线程安全用 PriorityBlockingQueue；
• offer/poll 为 $O(\log n)$，peek 为 $O(1)$；
• remove(Object) 为 $O(n)$（需线性查找）。

7.5 三语言优先队列对比

8. 堆的变体

8.1 d-ary 堆

d-ary 堆是二叉堆的推广，每个节点最多有 $d$ 个子节点：

• 索引公式（0-based）：$\text{child}_j(i) = d \cdot i + j + 1$（$j = 0, 1, \ldots, d-1$），$\text{parent}(i) = \lfloor (i-1)/d \rfloor$；
• 树高从 $\log_2 n$ 降至 $\log_d n$；
• 上浮更快 $O(\log_d n)$，下沉更慢 $O(d \log_d n)$（需比较 $d$ 个子节点）。

应用场景：

• $d = 4$（四叉堆）：Go runtime timer、netpoller 使用，平衡树高与子节点比较；
• $d = 8$：Dijkstra 算法在某些图结构下更优（缓存友好）；
• $d \to \infty$：退化为有序数组，插入 $O(1)$，删除 $O(n)$。

8.2 二项堆

二项堆（Binomial Heap）由 Vuillemin 1978 提出，是支持高效合并的可合并堆：

• 由多棵二项树 $B_0, B_1, \ldots, B_k$ 组成的森林；
• 二项树 $B_k$ 递归定义：$B_0$ 是单节点，$B_k$ 由两棵 $B_{k-1}$ 合并（一棵作为另一棵的最左子树）；
• $B_k$ 有 $2^k$ 个节点，高度为 $k$，深度 $d$ 处有 $\binom{k}{d}$ 个节点；
• $n$ 个节点的二项堆至多有 $\lfloor \log_2 n \rfloor + 1$ 棵二项树。

核心操作：

二项堆的合并操作是核心创新，远优于二叉堆的 $O(n)$ 合并。

8.3 Fibonacci 堆

Fibonacci 堆（Fibonacci Heap）由 Fredman-Tarjan 1984 提出，是理论最优的可合并堆：

• 基于二项堆，引入懒惰合并（lazy union）：合并时仅链接根链表，不立即归并；
• 节点被标记”失去过子节点”（marked），用于触发级联切割；
• 删除极值时才执行 consolidate 操作归并根；
• 节点度数上界用 Fibonacci 数列证明。

复杂度（均摊）：