> For the complete documentation index, see [llms.txt](https://datastructure-1.gitbook.io/datastructure-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://datastructure-1.gitbook.io/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/07-heap-and-priority-queue.md).

# 第 7 章：堆与优先队列

[<- 第 6 章　二叉搜索树](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/06-binary-search-tree.md) | [课程目录](/datastructure-docs/readme.md) | [第 8 章　平衡二叉树 ->](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/08-balanced-binary-search-trees.md)

> 所属模块：第四部分：树与二叉树\
> 对应实现：heap.cpp

### 本章导航

* [7.1 优先队列 ADT 与二叉堆的物理映射](#c07-7-1)
* [7.2 堆序性不变量与核心操作：上浮（SiftUp）与下沉（SiftDown）](#c07-7-2)
* [7.3 经典证明：为什么自底向上建堆只需 O(n)？（错位相减级数推导）](#c07-7-3)
* [7.4 原地堆排序（Heap Sort）算法精要与不稳定性剖析](#c07-7-4)
* [7.5 Top-K 问题经典模型：“门槛过滤器”与双堆求中位数](#c07-7-5)
  * [7.5.1 门槛模型：海量数据 Top-K 为什么用相反性质的堆？](#c07-7-5-1)
  * [7.5.2 对顶堆（双堆法）动态维护数据流中位数](#c07-7-5-2)
* [7.6 可并堆利器：左式堆（Leftist Heap）与零路径长（NPL）证明](#c07-7-6)
* [本章小结](#c07-summary)
* [思考题与经典大厂面试题](#c07-exercises)

***

## 第 7 章　堆与优先队列

> 难度：★★☆☆☆ | 代码：[heap.cpp](https://github.com/Huo0077/DataStructure/blob/main/heap.cpp)

**前置知识**：[第 5 章](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/05-binary-tree-basics.md) 完全二叉树的数组下标映射公式，[第 1 章](/datastructure-docs/di-yi-bu-fen-xu-lun/01-complexity-adt.md) 级数求和与复杂度分析。

**学习目标**：

1. 掌握完全二叉堆的数组索引映射不变量与堆序性质；
2. 掌握 `siftUp` 与 `siftDown` 的执行轨迹与边界防御；
3. 掌握自底向上建堆 (O(n)) 的严格数学推导；
4. 熟练运用“小顶堆求前 K 大 / 大顶堆求前 K 小”解决流式数据极值问题；
5. 理解左式堆通过牺牲右子树深度实现 (O(\log n)) 快速合并的理论机制。

***

### 7.1 优先队列 ADT 与二叉堆的物理映射

在许多应用中，我们并不需要对全体数据进行全局排序，而仅仅关心**当前最具优先级的元素（最大或最小）**。这种抽象数据类型被称为**优先队列（Priority Queue）**。

#### 二叉堆（Binary Heap）是优先队列最经典的实现：

1. **结构性质（Structure Property）**：它是一棵**完全二叉树**。因此，无需指针，直接使用紧凑的数组连续存储！
2. **下标映射规则（0-based）**：
   * 节点 (i) 的父节点：(\lfloor (i - 1) / 2 \rfloor)
   * 节点 (i) 的左孩子：(2i + 1)
   * 节点 (i) 的右孩子：(2i + 2)
3. **堆序性质（Heap-Order Property）**：
   * **大顶堆（Max Heap）**：任意节点的值 (\ge) 其任意孩子的值（根节点为全局最大值）；
   * **小顶堆（Min Heap）**：任意节点的值 (\le) 其任意孩子的值（根节点为全局最小值）。

```
               [10] (索引 0)
              /    \
      (索引 1)[7]   [8] (索引 2)
            /   \   /
     (3) [3]    [5][2] (5)

数组映射存储: [10, 7, 8, 3, 5, 2]  ─── 100% 紧凑，无指针开销，缓存极度友好！
```

***

### 7.2 堆序性不变量与核心操作：上浮（SiftUp）与下沉（SiftDown）

#### 1. 插入操作：尾部追加 + 上浮（SiftUp，O(log n)）

* 将新元素放入数组末尾（维持完全二叉树结构）；
* 若该元素大于其父节点，则与父节点交换；
* 沿着到根的唯一路径反复上浮，直至满足堆序或到达根节点。

#### 2. 删除堆顶：末尾替换 + 下沉（SiftDown，O(log n)）

* 堆顶元素即为最值，将其弹出；
* 将数组**末尾最后一个元素移到堆顶**（维持完全二叉树结构）；
* 此时堆顶往往破坏了堆序性。将当前节点与其**两个孩子中较大者**进行比对；若当前节点小于较大孩子，则两者交换；
* 反复下沉，直至满足堆序或成为叶子。

> **为什么下沉时必须与“较大”的孩子交换？**\
> 设根为 (X)，左孩子为 8，右孩子为 5。若 (X) 换到了右边（与较小的 5 交换），新根将变成 5，但 5 小于左孩子 8，依然破坏大顶堆性质！只有把较大的 8 换上去做新根，才能同时压制住 5 和下沉后的 (X)。

***

### 7.3 经典证明：为什么自底向上建堆只需 O(n)？（错位相减级数推导）

将一个包含 (n) 个无序元素的数组构建为大顶堆，有两种思路：

1. **连续插入建堆（自顶向下）**：从第 1 个元素开始依次执行 `push`（`siftUp`）。最坏复杂度为 (\sum\_{i=1}^n \log i = \Theta(n \log n))。
2. **自底向上建堆（Floyd 建堆法）**：直接把无序数组看作完全二叉树，**从最后一个非叶节点开始，逆序向前执行 `siftDown`**！

```cpp
void buildHeap(std::vector<int>& arr) {
    int n = arr.size();
    // 最后一个非叶节点下标为 (n - 2) / 2
    for (int i = (n - 2) / 2; i >= 0; --i) {
        siftDown(arr, n, i);
    }
}
```

#### 严格时间复杂度证明（错位相减法）：

* 设完全二叉树的高度为 (H = \lfloor \log\_2 n \rfloor)；
* 处于高度 (h) 的节点（叶节点高度 (h=0)），最多需要下沉 (h) 层；
* 高度为 (h) 的节点数至多为 (\lceil n / 2^{h+1} \rceil)；
* 所有节点下沉操作的总步数上界为： \[ S = \sum\_{h=1}^H \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot h \le \frac{n}{2} \sum\_{h=1}^H \frac{h}{2^h} ] 令级数 (A = \sum\_{h=1}^H \frac{h}{2^h} = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \dots + \frac{H}{2^H})。\
  两边乘以 2： \[ 2A = 1 + \frac{2}{2} + \frac{3}{4} + \frac{4}{8} + \dots + \frac{H}{2^{H-1}} ] 两式相减（错位相减）： \[ 2A - A = 1 + \left( \frac{2-1}{2} \right) + \left( \frac{3-2}{4} \right) + \dots + \left( \frac{H - (H-1)}{2^{H-1}} \right) - \frac{H}{2^H} ] \[ A = 1 + \left( \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^{H-1}} \right) - \frac{H}{2^H} = 1 + \left( 1 - \frac{1}{2^{H-1}} \right) - \frac{H}{2^H} < 2 ] 代回原式： \[ S \le \frac{n}{2} \cdot 2 = n = O(n) \quad \blacksquare ]

> **直观物理理解**：\
> 在树中，**绝大多数节点集中在最底层**（叶子占了近 (n/2)）。自底向上建堆时，海量的底层节点只需要下沉 0 步或 1 步；只有极少数的顶层节点（根节点只有 1 个）才需要下沉 (H) 步！“多劳者少，少劳者多”，总代价自然被收敛在线性 (O(n))！

***

### 7.4 原地堆排序（Heap Sort）算法精要与不稳定性剖析

堆排序由 J. W. J. Williams 于 1964 年发明，是唯一在最坏情况下兼具 **(O(n \log n)) 时间** 与 **(O(1)) 原地辅助空间** 的经典排序算法。

```
升序排序三部曲:
1. 将无序数组原地构建为【大顶堆】(耗时 O(n));
2. 将堆顶最大元素与当前堆末尾元素交换，堆有效大小减 1;
3. 对新堆顶执行 siftDown 恢复大顶堆性质;
4. 重复 2 和 3 直到堆大小为 1，整个数组便呈现严格升序!
```

#### 为什么堆排序是不稳定的？

在将末尾元素换至堆顶，或在下沉过程中，**相隔遥远的相同元素会被粗暴交换跨过彼此**。\
*例*：数组 `[5a, 5b, 3]` 构建大顶堆后仍为 `[5a, 5b, 3]`。第 1 轮将堆顶 `5a` 与末尾 `3` 交换，得到 `[3, 5b, 5a]`。此时 `5a` 已经排到了 `5b` 后面，原相对顺序彻底颠倒！

***

### 7.5 Top-K 问题经典模型：“门槛过滤器”与双堆求中位数

#### 7.5.1 门槛模型：海量数据 Top-K 为什么用相反性质的堆？

**经典面试题**：从 10 亿个浮点数中找出最大的 100 个数。内存仅能容纳数千个元素。

> **反直觉法则**：
>
> * **求前 K 个最大值** $\implies$ **维护大小为 K 的小顶堆**！
> * **求前 K 个最小值** $\implies$ **维护大小为 K 的大顶堆**！

**原因解释**：

* 小顶堆的堆顶是这 (K) 个候选人中的**最弱者（门槛值）**；
* 遍历后续数据流中的每个新元素 (x)：
  * 若 (x \le \text{堆顶})，说明它连候选人里最弱的都比不过，直接丢弃；
  * 若 (x > \text{堆顶})，说明它有资格晋级！淘汰当前堆顶，将 (x) 放入堆中并调整。
* 若使用大顶堆，堆顶是最大值，当来了一个新元素时，我们无法判断它是否比这 (K) 个数中最小的那个大，门槛机制完全失效！

#### 7.5.2 对顶堆（双堆法）动态维护数据流中位数

在流式数据中，数字不断流入，要求随时以 (O(1)) 时间返回中位数。

```
                  大顶堆 (存较小的一半)   小顶堆 (存较大的一半)
                      maxHeap                 minHeap
                       [ 5 ]                   [ 6 ]
                       [ 3 ]                   [ 8 ]
                       [ 2 ]                   [ 9 ]
                         ▲                       ▲
                         └───── 两个堆顶紧密咬合 ─────┘
```

**平衡不变量**：

1. `maxHeap` 存放较小的一半元素，`minHeap` 存放较大的一半元素；
2. 元素总数为偶数时，两堆大小相等；为奇数时，`maxHeap.size() == minHeap.size() + 1`；
3. `maxHeap.top() <= minHeap.top()` 恒成立。\
   **中位数查询**：若总数为奇数，直接返回 `maxHeap.top()`；若为偶数，返回两堆顶的均值！

***

### 7.6 可并堆利器：左式堆（Leftist Heap）与零路径长（NPL）证明

普通二叉堆若要合并两个大小为 (n) 的堆，必须将两数组拼接后重新建堆，耗时 (O(n))。为了以 (O(\log n)) 支持高效合并（`merge`），产生了**左式堆（Leftist Heap）**。

#### 零路径长（Null Path Length, NPL）：

* 节点 (x) 的 (\text{npl}(x)) 定义为从 (x) 出发到达一个\*\*不具有两个孩子的节点（外节点）\*\*的最短路径边数；
* 空节点的 (\text{npl}(\text{nullptr}) = -1)；叶子节点的 (\text{npl} = 0)；
* (\text{npl}(x) = \min(\text{npl}(x.\text{left}), \text{npl}(x.\text{right})) + 1)。

#### 左倾性质（Leftist Property）：

**对于树中任意节点 (x)，必有 (\text{npl}(x.\text{left}) \ge \text{npl}(x.\text{right}))。**\
*核心推论*：节点的 (\text{npl}) 完全由其**右孩子**决定：(\text{npl}(x) = \text{npl}(x.\text{right}) + 1)。

> **定理**：一棵包含 (r) 个右路径节点的左式堆，至少包含 (2^r - 1) 个节点。\
> 也就是说，**包含 (n) 个节点的左式堆，其右路径长度至多为 (\lfloor \log\_2(n + 1) \rfloor)**！

#### 递归合并核心：始终沿右路径深入！

```cpp
LeftistNode* merge(LeftistNode* h1, LeftistNode* h2) {
    if (!h1) return h2;
    if (!h2) return h1;
    // 保证 h1 根节点较小 (以小顶堆为例)
    if (h1->val > h2->val) std::swap(h1, h2);
    
    // 递归将 h2 合并到 h1 的右子树上
    h1->right = merge(h1->right, h2);
    
    // 若违反左倾性质，交换左右子树
    if (getNpl(h1->left) < getNpl(h1->right)) {
        std::swap(h1->left, h1->right);
    }
    // 更新当前节点的 npl
    h1->npl = getNpl(h1->right) + 1;
    return h1;
}
```

***

### 本章小结

1. **二叉堆是数组连续存储的巅峰之作**：完全二叉树的物理特性消除了指针开销与内存碎片。
2. **Floyd 建堆的精妙**：自底向上的下沉策略契约了“底层多、顶层少”的几何规律，以 (O(n)) 线性时间完成建堆。
3. **门槛模型是流式极值查询的屠龙刀**：小顶堆控大、大顶堆控小，对顶堆夹逼中位数。
4. **左式堆的非对称哲学**：通过主动把树的深度“左倾”，将右路径强行压缩至 (O(\log n))，化解了堆合并的线性诅咒。

***

### 思考题与经典大厂面试题

1. **d 叉堆（d-ary Heap）的时空折中**：若将二叉堆推广为每个节点拥有 (d) 个孩子的 (d) 叉堆，其 `siftUp` 和 `siftDown` 的时间复杂度分别是多少？在什么应用场景（例如 Dijkstra 稠密图）下 (d > 2) 的堆表现优于普通二叉堆？
2. **二叉堆的原地索引查询瓶颈**：标准二叉堆不支持以 (O(\log n)) 修改指定元素的值或删除指定元素（因为在数组中寻找该元素需要 (O(n))）。如何通过引入“反向索引映射数组（Inverted Index）”实现可索引优先队列（Indexed Priority Queue）？
3. **斜堆（Skew Heap）与左式堆的关系**：斜堆不维护任何 `npl` 字段，每次递归合并时无条件交换左右子树。请简述为什么斜堆能实现均摊 (O(\log n)) 的合并复杂度。