堆 | 自在学

堆：用局部有序换取稳定的优先级操作

如果任务总在问“当前最大的是谁”或“下一件最紧急的事是什么”，每次把全部元素重新排序就显得太重了。堆提供了一种更克制的方案：它不维护完整顺序，只保证父节点与子节点之间的大小关系。正是这点局部有序，让我们能在常数时间查看极值，并在对数时间内插入、删除或修改优先级。

本文统一讨论数组存储的二叉堆，代码采用 0-based 下标。最大堆是主线，最小堆只需反转比较方向。你会看到三个容易混淆却必须分开的对象：数组的实际长度、当前有效堆的大小，以及排序后已经退出堆的有序后缀。

堆究竟保证了什么

二叉堆同时受“形状”和“次序”两类约束。少了其中任何一个，后面的下标公式或复杂度结论都不再成立。

形状约束：完全二叉树

完全二叉树的每一层都从左到右填充。除最后一层外，其余层全部填满；最后一层可以不满，但节点不能在中间留下空洞。于是，按层次顺序保存节点时，数组一定是一段连续区间，不需要为空孩子存哨兵。

若非空堆有 $n$ 个元素，它的高度是

H = \lfloor \log_2 n \rfloor

这里的高度按“根到最深叶子的边数”计算。反过来，高度为 $H$ 的堆至少有 $2^H$ 个节点，至多有 $2^{H+1}-1$ 个节点。堆操作沿一条根到叶或叶到根的路径移动，因此路径长度至多是 $H$ ，也就是 $O(\log n)$ 。

次序约束：只比较父子

最大堆要求每个非根节点的键都不大于父节点：

A[parent(i)] \ge A[i]

沿祖先链反复使用这个关系，可以得到：任意子树的根都是该子树中的最大元素，整棵树的根就是全局最大元素。最小堆把不等号反过来，因此根是全局最小元素。

堆没有规定兄弟之间谁大，也没有规定左子树中的元素一定小于右子树中的元素。数组 [100, 60, 90, 20, 50, 80, 70] 是最大堆，但它既不是升序数组，也不是降序数组。

最大堆的完全二叉树形状与父子有序关系

若最大堆中的键互不相同，最小元素一定在叶子上。假如最小元素位于非叶节点，它至少有一个更小的孩子，这与“它已经是最小元素”矛盾。它不一定在数组最后一格，但不能出现在任意内部节点。

堆和“内存堆”不是一回事

这里的堆是一种维护优先级的数据结构。程序运行时用于动态分配对象的内存区域有时也叫“堆”，两者只共享名称，不共享结构和操作。二叉堆通常就是一个连续数组，并不要求每个节点单独动态分配。

小测

一个含 13 个元素的非空二叉堆，高度是多少？高度按边数计算。

关于最大堆，下列哪些结论必然成立？

树与数组如何一一对应

完全二叉树紧凑地填满层次顺序，因此数组下标本身就能表达父子关系。本文统一使用 0-based 下标。对合法节点 $i$ ：

parent(i) = \left\lfloor \frac{i-1}{2} \right\rfloor \quad (i>0)

left(i)=2i+1

right(i)=2i+2

根节点 $i=0$ 没有父节点，不能把 parent(0) 当作合法查询。孩子公式算出的下标若不小于 heapSize，对应孩子就不存在。

内部节点与叶子的边界

在长度为 $n$ 的非空堆中，所有叶子恰好位于

\left\lfloor \frac{n}{2} \right\rfloor,\left\lfloor \frac{n}{2} \right\rfloor+1,\ldots,n-1

若 $n\ge2$ ，最后一个内部节点是 $\lfloor n/2\rfloor-1$ 。这两个边界直接决定自底向上建堆从哪里开始。以 $n=10$ 为例，内部节点下标是 0..4，叶子是 5..9。

证明也很直接。节点 $i$ 至少有左孩子的条件是

2i+1<n

整数下标下，这等价于 $i<\lfloor n/2\rfloor$ ；不满足条件的下标便全部是叶子。

0-based 堆数组的父节点、左右孩子与叶子边界

数组长度不等于有效堆大小

普通优先队列中，数组里的每个元素通常都属于堆，此时 heapSize == A.size()。堆排序却会把最大元素逐个放到数组尾部。这些元素仍在数组中，但已经退出堆，所以必须只在 [0, heapSize) 内比较孩子。

text

数组：       [ 堆的有效区间 | 已排好序的后缀 ]
下标范围：   [0, heapSize)   [heapSize, A.size())

把 A.size() 错当成 heapSize，下沉时会把已经排好序的元素重新交换回堆中，排序结果随即失效。

交互演示：点亮一个下标

拖动滑块，观察数组位置、树节点以及父子下标如何同步变化。

小测

0-based 数组堆有 18 个元素，最后一个内部节点的下标是 ____。

堆排序过程中，孩子下标是否有效应与数组 A 的总长度比较。

向下修复为何只走一条路径

siftDown（也常称 maxHeapify）不是把任意乱序子树直接变成堆的万能函数。它有一个关键前提：待修复节点的左子树和右子树已经分别是最大堆，只有该节点与孩子之间可能违背堆序。

在这个前提下，我们比较“当前节点、左孩子、右孩子”三个候选者。如果当前节点最大，整棵子树已经合法；否则与较大的孩子交换。交换后，原来较小的值只可能在刚进入的那棵子树中继续违例，另一棵子树完全不受影响，因此算法只需沿一条路径向下。

最大堆向下修复时选择较大孩子并沿单路径下沉

可直接复用的迭代实现

cpp

#include <algorithm>
#include <cstddef>
#include <vector>
 
void siftDown(std::vector<int>& a, std::size_t i, std::size_t heapSize) {
    while (true) {
        const std::size_t left = 2 * i + 1

heapSize 采用半开区间语义：有效堆是 a[0..heapSize)。调用者要保证 i < heapSize <= a.size()。空堆不应调用本函数；单元素堆调用时会立即返回。

正确性为什么成立

可以把循环不变式写成一句话：每轮开始时，除当前下标 i 可能小于某个孩子外，当前子树的其他父子关系均满足最大堆序。

初始化时，这正是函数的前置条件：两棵孩子子树已经是堆。
若当前值不小于较大的孩子，它也不小于另一个孩子，当前节点和两棵孩子子树共同构成最大堆。
若当前值与较大孩子交换，新根拿到三者最大值，根部恢复合法；原值进入 largest 的位置，唯一可能的违例随下标一起下移，不变式得以保持。
每次交换至少下降一层。到达叶子或不再需要交换时，违例消失，函数终止。

对高度为 $h$ 的节点，最坏只下沉 $h$ 层，所以时间是 $O(h)$ ，在整堆根部调用时是 $O(\log n)$ 。若按子树规模写递推，较大孩子子树最多约占原子树的 $2/3$ ：

T(n) \le T(2n/3) + \Theta(1) = O(\log n)

存在让待修复值一路沉到叶子的输入，因此根部修复的最坏时间也是 $\Omega(\log n)$ ，合起来为 $\Theta(\log n)$ 。

必须与“较大的孩子”交换。若只看左孩子，或遇到一个更大的孩子就立刻交换，可能把更大的右孩子留在父节点下面，根部仍然违反最大堆序。

交互演示：一步一步下沉

下面的初始数组只有下标 1 的节点可能违例，它的两棵孩子子树已经是最大堆。每点一次“执行一步”，演示就完成一轮比较和交换。

小测

对最大堆执行向下修复时，当前节点同时小于左右孩子，应该与谁交换？

只要给出任意数组和任意下标，调用一次 siftDown 就能把整段数组变成最大堆。

自底向上建堆为什么是线性时间

给定一个无序数组，最自然的想法是从空堆开始逐个插入。这样当然正确，但第 $k$ 次插入可能上浮 $O(\log k)$ 层，总成本最坏为 $\Theta(n\log n)$ 。自底向上建堆直接利用了数组里已经存在的完全二叉树形状，把叶子视为天然合法的一节点堆，再逐层修复内部节点。

cpp

void buildMaxHeap(std::vector<int>& a) {
    // parentCount - 1 依次取 floor(n/2)-1, ..., 1, 0。
    // 循环变量始终大于 0 时才做减法，避免无符号下溢。
    for (std::size_t parentCount = a.size() / 2;
         parentCount > 0;
         --parentCount) {
        siftDown(a, parentCount - 1, a.size());
    }

当数组为空或只有一个元素时，a.size()/2 是 0，循环不会进入，结果自然正确。对 $n\ge2$ ，第一次传给 siftDown 的下标正是最后一个内部节点 $\lfloor n/2\rfloor-1$ 。

循环不变式给出完整正确性证明

在每轮处理下标 i 之前，保持下面的不变式：

下标 i+1 到 n-1 的每个节点，都是一棵最大堆的根。

初始化时，i = floor(n/2)-1。比它大的下标从 floor(n/2) 开始，全部是叶子；单个叶子没有需要检查的父子边，因此每个叶子都是最大堆的根。

处理 i 时，它的孩子下标都大于 i。由不变式可知，两棵孩子子树已经是最大堆，恰好满足 siftDown 的前置条件。修复后，节点 i 也成为最大堆的根，而后面的子树仍保持合法。

当下标 0 处理完毕时，根节点是最大堆的根，所以整个数组都满足最大堆序。完全二叉树形状始终由数组长度保证，不需要额外修复。

自底向上建堆的处理顺序与循环不变式

不能用“调用次数乘堆高”估出紧确结果

建堆确实调用约 $n/2$ 次 siftDown，单次上界也确实是 $O(\log n)$ ，所以 $O(n\log n)$ 是一个正确但宽松的上界。问题在于，大多数节点靠近树底，根本没有那么高的下沉路径。

设堆高为 $H$ 。深度为 $d$ 的节点不超过 $2^d$ 个，每个这样的节点最多下沉 $H-d$ 层。总下沉层数至多为

\sum_{d=0}^{H-1}2^d(H-d)

令 $k=H-d$ ，得到

2^H\sum_{k=1}^{H}\frac{k}{2^k} <2^H\sum_{k=1}^{\infty}\frac{k}{2^k} =2^{H+1}

又因为 $2^H\le n$ ，总工作量是 $O(n)$ 。直观上，能下沉很多层的节点非常少；数量庞大的底层节点只能下沉零层或一层。

线性建堆和逐个插入可能得到不同的合法堆。堆并没有唯一形态；只要完全二叉树形状和父子堆序成立，结果就是正确的。

小测

自底向上构建含 n 个元素的最大堆，最坏时间复杂度是多少？

自底向上建堆必须从最后一个内部节点向根倒序处理，原因有哪些？

堆排序如何维护两段边界

最大堆把当前最大值放在根。若把根与有效堆的最后一个元素交换，最大值就到了最终位置。接着把有效堆大小减一，并对新根向下修复，便能重复取出下一个最大值。数组由此逐渐分成左侧最大堆和右侧升序后缀。

cpp

void heapSort(std::vector<int>& a) {
    buildMaxHeap(a);
 
    for (std::size_t end = a.size(); end > 1; --end) {
        std::swap(a[0], a[end - 1]);
        siftDown(a, 0, end - 1

代码把 end 定义为有效区间的右开边界。每轮开始时，有效堆是 [0, end)；交换后，新后缀从 end-1 开始，所以传给 siftDown 的新 heapSize 是 end-1。

堆排序中最大堆缩小而升序后缀增长

排序循环的不变式

每轮开始时保持三件事：

a[0..end) 是最大堆；
a[end..n) 已按升序排列；
堆中的每个元素都不大于后缀中的每个元素。

初始化时，建堆让第一条成立，后缀为空，后两条自然成立。维护阶段把堆中最大值放到 end-1，它不大于原有后缀的第一个元素，因此扩展后的后缀继续升序；缩小后的堆只有根部可能违例，向下修复后第一条恢复。循环结束时 end=1，单元素前缀和有序后缀合起来就是完整升序数组。

复杂度、空间与稳定性

建堆是 $O(n)$ ，随后执行 $n-1$ 次至多 $O(\log n)$ 的向下修复：

T(n)=O(n)+(n-1)O(\log n)=O(n\log n)

使用迭代 siftDown 时，算法只需常数个临时变量，辅助空间是 $O(1)$ 。如果改成递归下沉，调用栈会占 $O(\log n)$ 空间。

堆排序通常不稳定。根与远端元素交换、下沉时跨层交换，都可能改变相等键记录的原始相对次序。它也不是自适应排序：即使输入已经升序或降序，标准实现仍要建堆并执行相同数量的取出轮次，渐近时间仍是 $\Theta(n\log n)$ 。

交互演示：观察边界向左移动

点击按钮后，每一步会把当前最大值放进右侧绿色有序区，并恢复左侧最大堆。

小测

使用最大堆进行原地升序排序时，每轮应把根与有效堆的最后一个元素交换。

关于标准堆排序，下列哪些描述正确？

优先队列把堆变成可用接口

优先队列维护一组带“键”的元素。键表示优先级，元素还可以携带任务、事件或记录本身。最大优先队列至少支持四个核心操作：

操作	含义	二叉最大堆时间
`maximum()`	查看最大键但不删除	$\Theta(1)$
`extractMax()`	删除并返回最大键	$O(\log n)$
`increaseKey(i, key)`	增大指定元素的键	$O(\log n)$
`insert(key)`	插入新元素	$O(\log n)$

最大值就在根，所以查看只需一次数组访问。删除根后，为维持完全二叉树形状，不能随便拿某个孩子补位；应把数组最后一个元素移到根，缩短数组，再向下修复。增大键只可能破坏它与父节点的关系，因此沿祖先链上浮。插入先把元素追加为最右叶子，再执行同样的上浮过程。

最大优先队列的查看、提取、增键与插入路径

一份包含边界检查的实现

cpp

#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <vector>
 
class MaxPriorityQueue {
private:
    std::vector<int> heap_;
 
    void siftUp(std::size_t i) {
        while (i > 0) {
            const std::size_t parent = (i - 1) /

extractMax() 单独处理单元素堆，避免弹出后再访问 heap_[0]。increaseKey() 先检查方向；若允许把键减小，就应改走向下修复。把两个方向混在一个接口中也可以：修改后与父节点比较，变大且超过父亲就上浮，否则向下修复。

上浮循环的不变式

增键后，唯一可能的违例是当前节点比父节点大。它与自己的孩子仍然合法，因为键只变大了。每次与父节点交换后，较大的新键上移；原父节点下移到孩子位置时，仍不小于该位置原来的其他孩子。于是唯一违例继续跟着新键向根移动，直到父节点不小于它或它成为根。

元素不只有一个数字时，要维护句柄

真实任务通常保存 (priority, payload, id)。若外部通过 id 调整优先级，需要额外维护 id -> 数组下标 的映射。每一次交换堆元素，都必须同步更新两个元素的下标映射，否则下一次 increaseKey 会改错对象。

二叉堆擅长找极值，却不擅长按任意键搜索。没有句柄时，为了找到某个指定任务，最坏仍要扫描 $O(n)$ 个元素；找到以后上浮或下沉才是 $O(\log n)$ 。

常见用法包括：最大优先队列安排最高优先级任务；最小优先队列按时间提取下一场事件；图算法用最小优先队列反复取当前距离最小的顶点并降低候选距离；合并 $k$ 个有序序列时，用大小至多为 $k$ 的最小堆保存各序列当前首项，总时间可达 $O(n\log k)$ 。

小测

最大优先队列删除根后，为同时保持完全二叉树形状，应先把哪个元素移到根？

优先队列元素带稳定 id，外部可按 id 修改优先级。实现时哪些做法正确？

接口与代价要一起选择

“堆”描述的是一类接口和次序约束，不等于只有一种内部结构。数组二叉堆结构简单，每次关键修改都有清楚的最坏上界。若工作负载极度偏向合并、插入和降低键，还可以考虑把多个最小堆有序树保留在一个根链表中，并把整理工作推迟到提取最小值时完成。

下面用最小堆接口作同向比较；最大堆只需反转大小关系。

操作	数组二叉堆（最坏）	延迟合并的树族堆（摊还）
创建空堆	$\Theta(1)$	$\Theta(1)$
插入	$\Theta(\log n)$	$\Theta(1)$
查看最小值	$Θ$

这里的“延迟合并的树族堆”通常称为 Fibonacci 堆。它把每棵树维持为最小堆有序，根节点放进可常数时间拼接的循环双向链表，并保存最小根指针。插入只是增加一棵单节点树，合并只是拼接根链表；提取最小值时才把同度数的树逐步链接起来。降低键若破坏父子关系，会切断节点并在必要时级联切断祖先。

数组二叉堆与延迟合并树族堆的接口代价对比

摊还常数不等于每次常数

摊还分析讨论一串操作的总成本。某次操作可以很贵，只要此前便宜操作积累的“余额”足以支付它，平均到整串操作后仍可能是常数。

树族堆可用势能直观表达这种余额。若 $t(H)$ 是根链表中的树数， $m(H)$ 是被标记的节点数，可取

\Phi(H)=t(H)+2m(H)

插入会增加一棵树，实际工作与势能增量都为常数。提取最小值虽然可能扫描并链接许多根，但每次链接都会减少树数，也就是释放此前积累的势能。降低键造成的级联切断可能单次很长，不过切断被标记节点会清除标记，势能下降可以支付这些步骤。因此“插入摊还 $\Theta(1)$ ”不能解释成“任意一次操作的最坏时间都是常数”。

为了让提取最小值的摊还时间保持 $O(\log n)$ ，还需要保证节点最大度数为 $O(\log n)$ 。级联切断的规则使一个度数为 $k$ 的节点必须拥有至少按 Fibonacci 数增长的子树规模，因而其子树大小至少呈指数增长：

size(x) \ge F_{k+2} \ge \varphi^k

其中 $\varphi=(1+\sqrt5)/2$ 。因为 size(x) <= n，所以

k\le \log_{\varphi}n=O(\log n)

这个比较只是在回答“换一种内部结构能否改变某些接口的代价”。日常优先队列若不频繁合并，也没有海量降低键操作，数组二叉堆通常更直接：常数因子小、连续内存友好、代码和边界更容易验证。树族结构适合对摊还界有明确需求的工作负载，代价是更多指针、标记和复杂维护逻辑。

最后的实现检查单

先固定最大堆或最小堆，并让所有比较方向一致。
明确使用 0-based 还是 1-based 下标，不要混用公式。
所有孩子判断都与有效 heapSize 比较。
向下修复前确认两个孩子子树已经成堆。
自底向上建堆从最后一个内部节点倒序到根。
空堆、单元素堆、重复键和下标越界都要单独验证。
元素交换时同步维护外部句柄；复杂度表要注明最坏、期望还是摊还。

小测

某种堆的插入操作为摊还 O(1)，意味着每一次插入的最坏时间都必须是 O(1)。

工作负载不需要合并堆，规模中等，并且更看重实现简单、连续内存和清晰的单次最坏上界，通常先选择哪种结构？

(

1

)

\Theta(1)