树系列第 16 篇：堆与优先队列

本文是”树系列”的第 16 篇。前面我们花了大量篇幅研究二叉树：第 13 篇讲了 B 树为什么存在，第 14 篇讲了 B+ 树在磁盘上的表演。今天我们把注意力拉回内存里最普通也最实用的一棵二叉树——堆（Heap）。别被名字吓到，堆并不是一座”堆积木”的乱山，而是一棵被两条纪律管得服服帖帖的完全二叉树：所有节点都按层从左到右排好，并且每个父亲都遵守一条”对子优先”的规矩。把这两条纪律翻译成代码，就是一句话的事：把树装进数组，用下标算亲戚。本篇会从”为什么总有人急着要最大/最小”这个问题出发，一步一步带你把上浮、下沉、建堆、堆排序、优先队列、Top-K 全部走一遍。读完之后你会发现，堆是整个数据结构世界里少有的”算法又简单、效果又惊人”的选手：五行的上浮、五行的下沉，加起来不超过二十行代码，却能撑起 Dijkstra 最短路、任务调度、海量数据 Top-K 一整片应用天空。

0 先把第 3 篇和第 4 篇的结论捡回来

如果你是按顺序读到这里的，可能已经对两个老朋友有了印象：完全二叉树（complete binary tree）和数组存储（array storage）。第 3 篇里我们说过，完全二叉树是这样一棵二叉树：除了最后一层之外，每一层都被节点塞得满满的；最后一层可以不满，但必须从左到右连续地住人，中间不许出现”空一格、住一格、再空一格”的跳号情况。也就是说，如果你从根开始，按”先从上到下、再从左到右”的顺序给节点编号，那么编号一定是连续的 1、2、3、4……直到最后一个节点，绝对不会跳过任何一个号码。

第 4 篇我们进一步发现，完全二叉树和数组是天生一对。普通二叉树用数组存会有灾难性的空间浪费——一棵只有右孩子的”右斜链”，30 个节点可能要开十亿个格子的数组；而完全二叉树不一样，它的节点编号本身就是连续的，直接把第 i 号节点放进数组的第 i 个位置（1 基下标），恰好一个格子都不浪费。更妙的是，父子关系不需要指针：第 i 号节点的父亲在下标 i/2（向下取整）处，左孩子在 2i 处，右孩子在 2i+1 处。一道算术题，代替了整张关系网。 这两句话就是今天整篇文章的地基。如果你对”完全二叉树为什么能塞进数组”还有一丁点犹豫，请先回到第 3、4 篇把编号规则再画一遍：一棵 7 节点的完全二叉树，编号 1 到 7，左孩子永远是父亲编号的两倍，右孩子永远再加一。这个规律不是巧合，而是”每一层节点数翻倍 + 编号连续”共同保证的数学事实。下面我们就要利用它，把”取最大/最小”这件事做到极致。

1 问题：总是要”最大/最小”的那个

1.1 一个真实到骨子里的需求

先离开教科书，想三个生活场景。

第一个场景：医院急诊科。病人不断到来，但医生只有一个。病情有轻重缓急：心脏骤停的人必须立刻抢救，感冒发烧的人可以等半小时。如果医生按”谁先来谁先看”的顺序接诊，那叫排队（FIFO）；但急诊的真实规则是”谁最危重谁先看”，危重程度随时会变。医生需要的不是”最早来的”，而是”目前最危重的”。

第二个场景：操作系统里的进程调度。你的电脑同时在跑浏览器、编译器、杀毒软件、后台更新，CPU 每一毫秒都在做选择：下一个该执行哪个进程？理想调度器不是按创建顺序轮流来，而是按”优先级”来：交互程序优先级高，批处理任务优先级低。而且进程的优先级会动态变化——用户正盯着窗口打字时，这个窗口的优先级就该立刻提高。

第三个场景：排行榜。一个游戏每天产生百万条玩家分数，运营想看”当前最高的前十名”。注意，这个需求不是”把全体数据排好序”，而是”只关心头部的少数几个”。为了十个名额把百万条记录全部排序，听起来就像为了找一颗最大的珍珠，把整个养殖场翻了个底朝天。

三个场景看似风马牛不相及，内核却一模一样：数据在不断加入，我们每次只想要当前最大（或最小）的那一个。这种需求有一个专门的名字——优先队列（Priority Queue）。它和普通队列的差别只有一个字：普通队列按”先来后到”出队，优先队列按”优先级高低”出队。你插入一个元素，它不会老老实实站在队尾，而是按自己的”分量”找到属于自己的位置；你弹出队首，得到的永远是当前全队”最重”的那位。

那么问题来了：实现一个”总能把最大/最小元素快速取出来”的结构，用我们已经学过的老办法行不行？

1.2 用数组实现，代价是什么

数组是最老实的数据结构：按下标访问 O(1)，但插入和删除都要挪动元素。我们分两种情况讨论。

第一种，无序数组。插入很好办，直接往末尾追加，O(1) 完成；但取最大值就惨了，必须从头到尾扫一遍，O(n)。如果业务是”插入频繁、取最大偶尔一次”，无序数组还能凑合；但急诊科和任务调度是”取一次、插很多次、再取一次”的循环，每次取最大都要全量扫描，百万条数据就是百万次比较，显然不行。

第二种，有序数组（比如从小到大排好）。取最大变成 O(1)——最后一位就是答案；插入却要二分找到位置，然后把后面的元素整体右移，最坏 O(n)。调度器一秒钟插入几百个进程，每次 O(n) 的搬移足以让系统卡成幻灯片。

一句话总结：数组要么”插得快、取得慢”，要么”取得快、插得慢”，永远无法两头都占到。

1.3 用链表实现，代价是什么

链表比数组灵活：插入一个节点只要 O(1)（如果有指针在手），不需要搬移数据。但链表最怕随机访问：找第 k 个节点必须从头走 k 步。想维护”最大值”，我们可以在插入时做”插入排序”式的操作——从头开始，找到第一个比它小的节点，把它插进去，保持全链有序。这样取最大是 O(1)（头节点就是），插入却平均 O(n)。如果偷懒做无序链表，插入 O(1)、取最大 O(n)，又回到了和数组对称的困境。

更重要的是，链表在内存里是”东一块西一块”的，缓存命中率远不如数组。真实世界里，连续内存的遍历速度可能比散乱指针快一个数量级。链表并没有真正解决”两头都要快”的问题，只是把搬移换成了行走。

1.4 用二叉搜索树实现，代价又是什么

到这里你可能会拍大腿：我们不是刚学完 BST 吗？BST 的插入平均 O(log n)，取最大就是一路往右走到叶子，也是 O(log n)，两头都不差，为什么还要发明堆？

这个问题问得非常好。BST 确实能当优先队列用，而且很多语言库里确实有人这么干（Java 的老版本 TreeMap 就能模拟）。但 BST 有四个不容忽视的毛病：

第一，最坏情况。BST 只有在”随机插入”时才平均 O(log n)，一旦输入有序（比如从小到大依次插入），树就会退化成一条右斜链，插入和取最大都变 O(n)。要避免退化，就得引入 AVL、红黑树那套旋转机制，代码量立刻翻几倍。

第二，代码复杂度。BST 的删除要处理”没有孩子、一个孩子、两个孩子”三种情况，两个孩子时还要找后继节点；堆的删除堆顶却只需要”把最后一个元素放上去再往下沉”，逻辑简单得多。

第三，局部性差。链式 BST 的节点散落内存，访问一条从根到叶子的路径，每次跳指针都可能缓存未命中；堆住在数组里，下标 i、2i、2i+1 在内存里挨得很近，访问路径是连续的整数，对缓存极其友好。

第四，空间开销。每个 BST 节点要存值、左指针、右指针（可能还有 parent、颜色字段），而堆只需要一个数组，连”孩子是谁”都不需要记录，公式一算就出来了。

你看，BST 输的不是”平均性能”，而是”稳定性、简单性和工程友好性”。堆正是冲着这三点来的：它只维护”部分有序”，不需要全局有序，所以插入和删除都能在 O(log n) 内完成，而且最坏情况就是 O(log n)，没有退化这一说。

2 堆的定义：完全二叉树 + 堆序性质

2.1 两条纪律，把堆框死

**堆（Heap）**是这样一种数据结构：

纪律一（结构）：堆是一棵完全二叉树。 这意味着它住在数组里几乎不浪费空间，并且节点编号连续、下标公式成立。这一条我们在第 3、4 篇已经反复练过，它管的是”形状”。

纪律二（堆序）：每个节点的值都不大于（或不小于）它的所有后代。 更常用的是只对”父子”下约束：每个节点的值都不大于（或不小于）它的直接孩子。等一下，“所有后代”和”直接孩子”这两个说法等价吗？答案是等价的，因为父子关系可以传递：如果父亲不小于孩子，孩子的孩子又不小于它的孩子，那么一路推下去，根就一定是整棵树里最大的。这就是”只保证父子关系就够”的底气——堆序性质是一条可以沿着树往下传递的链，你不需要记住每个节点的所有后代，只要检查每一对父子，全局的最大值/最小值就会自动”浮”到根上。

大顶堆（Max-Heap）：父亲的值 ≥ 两个孩子的值。根是最大值，所以也叫”大根堆”。

小顶堆（Min-Heap）：父亲的值 ≤ 两个孩子的值。根是最小值，也叫”小根堆”。

注意一个容易踩的坑：堆不要求兄弟之间有序。大顶堆里，左孩子可以比右孩子大，也可以比右孩子小，随你喜欢；堆只约束”上下”（父子），不约束”左右”（兄弟）。正因为放弃了兄弟之间的顺序，堆才能比 BST 更”松”，插入和删除才不需要旋转。

下面两个例子，左边是大顶堆，右边是小顶堆。请仔细看：兄弟之间没有固定的大小关系，但每一对父子都守规矩：

大顶堆里，42 比 35 大，但 35 放在右子树的位置并不违反规则，因为 35 是 42 的孩子，42 ≥ 35 成立；30 与 42 是兄弟，谁大谁小根本不归堆管。小顶堆同理：5 和 3 是兄弟，3 比 5 小也没关系，只要 1 不大于它们俩就行。

2.2 “只保证父子关系”为什么就够用

这是初学者最容易产生怀疑的地方：堆这么”松”，凭什么保证取最大/最小是 O(1)？答案在于根节点。

因为每一对父子都满足”父亲 ≥ 孩子”，所以根节点的值一定不小于它的两个孩子；两个孩子又各自不小于它们的孩子……把这条链一直推到所有叶子，根就同时不小于每一个节点。换句话说，大顶堆的根就是全堆最大，小顶堆的根就是全堆最小。取最大/最小只需要读 a[1]，O(1) 搞定，连搜索都不用。

你可能会接着问：那堆里”第二大的”在哪？很遗憾，没人知道——它可能是左孩子，也可能是右孩子，还可能藏在某个子树的深处。堆只承诺”最大值在根”，不承诺其他任何排名。这正是”部分有序”的含义：信息按需保存，你只关心最大/最小，堆就只为你维护这一个答案。 你不需要兄弟之间排好序，因为兄弟顺序对”谁是最大”毫无贡献。想通这一点，堆的设计哲学你就抓住了：少维护一分秩序，就少付一分代价。

2.3 一个必须分清的概念：堆和堆内存

在中文技术圈，“堆”这个词有个著名的双关：数据结构里的堆（heap）和操作系统里的”堆内存”（heap memory）完全不是一回事。堆内存是程序运行时动态分配对象的一片区域，它的名字来自早期的内存分配器，跟”完全二叉树”没有关系。C 语言里 malloc、Java 里 new 的对象都来自”堆内存”，但那里面的对象并不满足任何堆序性质。本篇说的堆，一律指数据结构。

还有一个近亲概念：优先队列是抽象接口，堆是具体实现。优先队列定义了三个操作——插入、取最大/最小、删最大/最小；堆只是实现这三个操作的最经典方案。用 BST、跳表、甚至有序数组也能实现优先队列，只是代价不同。很多语言里”PriorityQueue”的名字直接和堆绑定，但概念上请记住：接口是需求，堆是答案。

2.4 堆到底”有序”在哪：三条能保证，三条不能保证

学堆的人常常产生一种朦胧的错觉：“堆是不是已经差不多有序了？“为了消灭这种错觉，我们把堆能保证和不能保证的性质各列三条。

堆能保证的：

第一，根是全局极值。大顶堆的根是最大值，小顶堆的根是最小值，这是堆序性质沿着父子链传递的必然结果。

第二，每条”祖先链”是单调的。从根到任意叶子，路径上的值在大顶堆里严格非增（或非严格递减）：父亲 ≥ 孩子 ≥ 孙子……这条链虽然不保证”相邻层之间”之外的任何事，但它是堆序性质的直接表达。

第三，形状是完整的完全二叉树。最后一层不满，但空缺只允许出现在最右侧，编号永远连续。这个形状保证树高 O(log n)，也保证数组零浪费。

堆不能保证的：

第一，兄弟之间没有顺序。左孩子可以比右孩子大，也可以比右孩子小。你以为”堆已经排好序”时，一画出来就会发现同一层乱七八糟。

第二，“上层一定大于下层”不成立。堆只约束父子，跨层的两个节点之间没有任何可比关系；第三层的一个节点完全可能比第二层的另一个节点大（我们建堆的例子里就出现过 9 在第三层、5 在第二层的局面）。

第三，第 k 大的位置没有规律。除了最大值固定在根，第二大的位置不确定，中位数的位置更不确定。如果你想查”第 k 大”或”中位数”，要么循环 poll k 次（O(k log n)），要么额外维护别的结构（比如双堆），堆本身帮不上忙。

记住这三条”能”和三条”不能”，你对”部分有序”的理解就及格了。堆的哲学从来不是”知道一切”，而是”把最关键的那个极值永远放在伸手就够得着的地方”。

3 数组表示：把树”压”进一维数组

3.1 编号与下标的对应

第 4 篇已经说过，完全二叉树可以按”层序”编号。我们约定从 1 开始编号（第 1 号是根），于是整棵树可以一字排开住进数组。下面这棵 10 节点的完全二叉树，编号和数组下标完全重合：

对应的数组长这样（1 基下标，下标 0 空着或者放哨兵）：

下标:  0   1   2   3   4   5   6   7   8   9  10
数值: [—, 90, 80, 70, 60, 50, 40, 30, 20, 10, 15]

把树和数组并排摆在一起，你会发现一个奇妙的对应关系：树里的”左一步”，就是数组里的”下标乘二”；树里的”右一步”，就是”下标乘二加一”；树里的”回一步”，就是”下标除二取整”。 整棵树的边，全部被算术运算代替。

3.2 三条下标公式

设 i 是某个节点的下标（1 基），则：

父亲下标：parent(i) = ⌊i / 2⌋（向下取整） 左孩子下标：left(i) = 2i 右孩子下标：right(i) = 2i + 1

验证一下上面那棵树：节点 5 的值是 50，它的父亲是 ⌊5/2⌋ = 2，a[2] = 80，正确；它的左孩子是 10，a[10] = 15，正确；右孩子是 11，但数组长度只有 11（下标 0 到 10），说明 11 不存在——公式算出来越界，就等于”没有这个孩子”。节点 9 的父亲是 ⌊9/2⌋ = 4，a[4] = 60，正确。

这三个公式在代码里写出来就是三行：

const parent = (i: number) => i >> 1;        // 等价于 Math.floor(i / 2)
const left   = (i: number) => i << 1;        // 等价于 i * 2
const right  = (i: number) => (i << 1) | 1;  // 等价于 i * 2 + 1

为什么要用位运算？因为整数乘 2、除 2 在计算机里就是移位，快得一眨眼；不过这只是锦上添花，你完全可以直接写 i / 2 和 i * 2，语义更直白。本文后面的代码为了可读性，直接用乘除和 Math.floor，位运算写法留给你自己做性能优化时用。

3.3 heapSize 与数组长度：两个绝不能混淆的数

这是堆实现里最容易翻车的一个细节。数组长度（array length）是”格子总数”，而**堆大小（heapSize）**是”当前实际住着多少个元素”。

为什么两者会不一样？因为堆在运行中不断插入、删除。插入时可能先往数组末尾追加，数组长度变大；删除堆顶后，我们通常把最后一个元素挪到堆顶，然后 heapSize 减一——此时数组末尾那个格子里的旧值并没有被物理清空，它只是”不属于堆”了。更常见的是预留容量：一开始就 new 一个 capacity 为 16 的数组，里面只放了 5 个元素，heapSize = 5，array.length = 16。所有操作（上浮、下沉、比较孩子）只看下标 < heapSize 的格子，下标 ≥ heapSize 的区域视为”空房子”，视而不见。

一句话总结：heapSize 是”逻辑边界”，数组长度是”物理边界”。写代码时，凡是”找孩子、找父亲、和兄弟比较”，都要先问一句：这个下标在 heapSize 之内吗？越界就说明那个位置没有节点。把这条纪律刻进脑子里，后面所有算法都不会写错边界。

还有一个语言细节：很多语言的数组从 0 开始，而我们的公式从 1 开始。两种方案都能实现堆：0 基时父是 ⌊(i-1)/2⌋，左子是 2i+1，右子是 2i+2，公式稍微丑一点，而且”0 号节点的父亲”计算起来很尴尬。为了公式漂亮，本文统一使用 1 基下标：数组下标 0 空着不用（或者放一个哨兵值）。实际工程里两种都有，面试时先跟考官确认你的下标约定，能省掉一大半边界 bug。

3.4 下标公式为什么成立：一次直觉证明

“左孩子是 2i”这条公式很多人背得滚瓜烂熟，但从未想过它为什么成立。我们花一小节把它证明出来，从此公式不再是死记硬背。

考虑一棵完全二叉树，节点按层序编号（1 基）。关键观察是：完全二叉树每一层的节点都从左到右连续排列，所以”第几个节点”和”它在哪一层”之间有精确的换算关系。 第 1 层最多 1 个节点，第 2 层最多 2 个，第 3 层最多 4 个……第 k 层最多 2^(k-1) 个。

现在看第 i 号节点。它所在的那一层（假设是第 d 层）之前的全部层，如果都塞满，一共有 1 + 2 + 4 + … + 2^(d-2) = 2^(d-1) - 1 个节点（等比数列求和）。也就是说，第 d 层从编号 2^(d-1) 开始。节点 i 在这一层内部排第几个？第 (i - 2^(d-1) + 1) 个（从 1 数起）。

它的左孩子在第 d+1 层。第 d+1 层在第 d 层之前一共有 2^d - 1 个节点；而左孩子的”排名”和父亲的”排名”之间有一个确定的关系：第 d 层第 j 个节点的左孩子，是第 d+1 层第 2j-1 个节点（每个父亲生两个孩子，两个孩子的位置是 2j-1 和 2j）。把 j = i - 2^(d-1) + 1 代入，左孩子编号 = (2^d - 1) + (2j - 1) = 2^d + 2j - 2 = 2^d + 2(i - 2^(d-1) + 1) - 2 = 2^d + 2i - 2^d + 2 - 2 = 2i。左孩子正好是 2i！ 右孩子再加一，就是 2i+1。父亲是逆运算，⌊i/2⌋。

这个证明看起来绕，其实核心只有一句话：完全二叉树里，每层人数翻倍，所以”父亲的编号”和”孩子的编号”之间天然差一个 2 倍的关系。 你不需要每次推导，但做过一次之后，你会在任何下标约定面前都不慌：0 基时同理可证，父是 ⌊(i-1)/2⌋，左子是 2i+1——因为”从 0 开始数”只是把整条编号链平移了一格。

还有一个容易误解的点：公式对”任意二叉树按层序编号”也成立（左孩子确实在下标 2i 处），但普通二叉树的编号会跳号——比如某个节点只有右孩子，它的左孩子位置空着，编号序列就断了。这时公式依然”算得对”，但数组必须给空位留格子，空间就浪费了。所以准确的说法是：公式是层序编号的必然结果，而”完全”二字保证编号连续、数组不浪费。 两者缺一不可。

4 核心操作一：上浮（siftUp）

4.1 场景：插入新元素

假设现在有一个合法的大顶堆，里面住着 7 个元素：

现在来了一位新客：65。插入规则的第一条是”保持完全二叉树”——结构纪律不能破坏，所以我们只能把新元素放在”层序编号的下一个空位”，也就是第 8 号位置：4 号节点（30）的左孩子。这一步叫”插到末尾”，在数组里就是 a[++heapSize] = 65。

但插完以后堆序性质被破坏了：新元素 65 的父亲是 ⌊8/2⌋ = 4 号节点，也就是 30。大顶堆要求父亲 ≥ 孩子，而 30 ≥ 65 不成立，违规！怎么补救？最自然的想法是：让 65 和它的父亲交换位置，把 65 往上提一层。交换后 65 在 4 号位，30 在 8 号位：

现在检查父子关系：65 的父亲是 30，而大顶堆要求父亲 ≥ 孩子，30 ≥ 65 不成立，违规！怎么补救？最自然的想法是：让 65 和它的父亲交换位置，把 65 往上提一层。交换后 65 在 4 号位，30 在 8 号位：

换完还要再检查：65 的新父亲是 50（⌊4/2⌋ = 2），50 ≥ 65 又不成立，继续换。65 再上一格，和 50 交换：

再检查：65 的新父亲是 70，70 ≥ 65 成立，或者 65 已经到根了——两种情况都意味着”上浮结束”。最终 65 停在第 2 层，堆重新合法。这个过程就是上浮（siftUp / bubbleUp / swim）：新元素像气泡一样，一路和父亲比大小，比父亲大就换，直到遇见更大的祖先或抵达根。

4.2 上浮的完整过程图

把刚才四张图串成一张流程图，你就能看到上浮的本质是一个”循环交换”：

注意，这是大顶堆的版本，比较符号是”x 大于父亲才交换”。小顶堆把大于号换成小于号即可。

4.3 上浮的代码与逐行解释

function siftUp(heap: number[], i: number): void {
  while (i > 1) {                       // 第 1 行：只要还没到根
    const p = Math.floor(i / 2);        // 第 2 行：算父亲下标
    if (heap[p] >= heap[i]) break;      // 第 3 行：父亲不小，规矩成立，停
    [heap[p], heap[i]] = [heap[i], heap[p]]; // 第 4 行：否则交换父子
    i = p;                              // 第 5 行：i 上移一层，继续检查
  }
}

逐行拆解：

第 1 行：循环条件 i > 1。根的下标是 1，当 i 等于 1 时说明新元素已经浮到根，它没有父亲，循环自然结束。这一步也顺便处理了”空堆插入第一个元素”的情况：第一个元素插在 1 号位，i = 1，循环根本不进，完美。

第 2 行：用公式算父亲下标。1 基下标下，父亲就是 i 除以 2 向下取整。比如 i = 8，父亲是 4；i = 4，父亲是 2；i = 2，父亲是 1。

第 3 行：检查堆序。大顶堆要求父亲 ≥ 孩子，如果 heap[p] ≥ heap[i] 已经成立，说明当前这一对父子没问题；而且更妙的是，父亲以上的部分本来就没被破坏过——因为父亲在交换前是合法的，它比自己的父亲小（或者它自己就是根），现在新元素还没超过它，所以祖先链全部安全。因此可以放心 break。这就是”只检查父子、上浮到一处就停”的正确性来源。

第 4 行：父子交换。这里用了 ES6 的解构赋值，一行交换两个数。交换后，新元素住进父亲的位置，原来父亲被挤到孩子的坑里。

第 5 行：把当前下标更新为父亲下标，继续往上一层检查。循环回到第 1 行，重复”算父亲、比大小、决定交换”。

有人会问：第 3 行能不能改成”等号也交换”？不能，也没必要。相等时交换除了浪费 CPU，还可能破坏后续”稳定”相关的性质（堆排序章节会讲到稳定性问题）。所以比较时用 ≥ 或 ≤ 直接 break，保留相等元素的原位。

4.4 上浮的复杂度

上浮每循环一次，下标 i 就除以 2，最多循环树高次。n 个节点的完全二叉树高度是 O(log n)，所以上浮最坏 O(log n)，平均也是 O(log n)（最坏情况是所有祖先都小于新元素，比如新元素比全堆都大，它要一路浮到根）。最好情况 O(1)：新元素比父亲小，一次比较就停下。空间复杂度 O(1)，只有几个临时变量。

4.5 上浮实战纠错：四个最常见的翻车现场

上浮代码只有五行，但翻车方式比代码行数还多。把下面四个错误提前排雷，你的堆实现就能一次写对。

错误一：忘了更新 i，陷入死循环或只交换一次。 很多新手写完交换就结束循环体，忘了 i = p。结果要么程序陷入无限循环（i 永远是同一个值，条件永远成立），要么只交换一层就停下，堆序根本没修好。检查方法很简单：在纸上走一遍插入，确认 i 每一步都在往根的方向减半。

错误二：比较符号写反。 大顶堆应该”父亲 ≥ 孩子就停”，小顶堆应该”父亲 ≤ 孩子就停”。如果把大顶堆写成 heap[p] < heap[i] 才交换（这是对的），却在 break 条件里写成 heap[p] < heap[i] 就停，逻辑恰好反过来，堆会在第一次插入时就坏掉。写完后用”新元素比全堆都大”和”新元素比全堆都小”两个极端用例各测一遍，符号问题立刻暴露。

错误三：边界用错。 有人把 while (i > 1) 写成 while (i >= 1)，根节点 1 号会继续计算 p = 0，访问 a[0]。如果 a[0] 恰好是个很大的垃圾值，堆序判断会变得莫名其妙；如果 a[0] 是哨兵正无穷，程序反而”碰巧”能跑，但这种巧合掩盖了逻辑错误，更危险。记住：根没有父亲，循环到 i = 1 就必须停。

错误四：插入调用了下沉。 插入的新元素在数组末尾，它的两个孩子根本不存在（或者还住着废墟），下沉逻辑面对它时无从谈起；正确姿势永远是”末尾 + 上浮”。反过来，把最后一个元素搬到堆顶后，它没有父亲可依靠（或者父亲在上层已合法），正确姿势是”堆顶 + 下沉”。插入配上浮、删除配下沉，这条口诀永远不要记反。

顺带一提，调试堆代码时最有效的工具不是打印中间值，而是写一个 isValidHeap() 校验函数：遍历所有 i ∈ [1, heapSize]，逐个检查”左孩子存在时父亲 ≥ 左孩子、右孩子存在时父亲 ≥ 右孩子”。每轮操作后调用它，任何 bug 都会在第一次出现时被当场抓住。

到这里，插入的”调整”部分已经完成。但先别急着庆祝——上浮只是堆操作的左半边天，我们还需要它的镜像操作：下沉。

5 核心操作二：下沉（siftDown）

5.1 场景：删除堆顶

删除堆顶是优先队列的核心动作：弹出当前最大（或最小）值。但”删除”有一个结构难题：如果直接删掉根，树就断成两截，怎么补都补不成一棵完全二叉树。

聪明的办法是**“换人”**：先把根和最后一个元素交换（或者直接说”把最后一个元素抄到根上”），然后把堆大小减一，这样被删掉的最大值就被”隔离”在数组末尾的废墟区，而完全二叉树的形状依然完好。代价是：现在站在根上的，是一个从底部调上来的”小个子”，它很可能不配当根——堆序被破坏了。

请看下面的例子。大顶堆 [70, 50, 40, 30, 20, 10, 25]：

第一步，把 70 弹出（拿走答案），把最后的 25 搬到根上，heapSize 从 7 变成 6：

现在 25 在根上，它有两个孩子 50 和 40。大顶堆要求根 ≥ 孩子，可 25 比 50 小，违规。和上浮”只和父亲比”不同，下沉要在两个孩子的竞争中选出更合适的那一个：50 和 40 里，50 更大，如果把 25 和较小的 40 交换，40 到了 2 号位，2 号位的父亲是根（25），25 ≥ 40 还是成立不了，白换；只有和较大的孩子 50 换，交换后根变成 50 ≥ 25，这一对父子才合法。所以规则是：下沉时，先挑出两个孩子里更大的那个（大顶堆），再和它比较、决定是否交换。

交换 25 和 50：

25 现在在 2 号位，它又有两个孩子 30 和 20。两个孩子里更大的是 30，25 < 30，继续交换：

25 在 4 号位，左孩子是 8 号位（已经超出 heapSize = 6，不存在），右孩子更不存在。没有孩子，下沉停止。 最终堆变成 [50, 30, 40, 25, 20, 10]，每一项父子关系都合法：50 ≥ 30、50 ≥ 40、30 ≥ 25、30 ≥ 20、40 ≥ 10。删除堆顶完成。

5.2 下沉的完整过程图

5.3 下沉的代码与逐行解释

function siftDown(heap: number[], i: number, heapSize: number): void {
  while (2 * i <= heapSize) {              // 第 1 行：有左孩子才继续
    let child = 2 * i;                     // 第 2 行：先假定左孩子更大
    if (child + 1 <= heapSize && heap[child + 1] > heap[child]) {
      child++;                             // 第 3-4 行：右孩子存在且更大，改选右
    }
    if (heap[i] >= heap[child]) break;     // 第 5 行：父亲已不小于较大孩子，停
    [heap[i], heap[child]] = [heap[child], heap[i]]; // 第 6 行：交换
    i = child;                             // 第 7 行：下沉到孩子位置继续
  }
}

逐行拆解：

第 1 行：循环条件 2i ≤ heapSize。在 1 基完全二叉树里，左孩子下标是 2i；如果 2i 已经超出堆大小，说明 i 是叶子，没有孩子可换，下沉结束。这个条件同时天然处理了”堆里只有一个元素”和”i 是最后一个节点”的情况。

第 2 行：先假设”较大的孩子”是左孩子，记下它的下标。为什么是”较大”而不是”第一个”？因为大顶堆要保证父亲 ≥ 每个孩子，所以必须和两个孩子里较大的那个比——和较大的比赢了，另一个自然更赢不了；和较大的换，另一侧也绝不会出问题。

第 3-4 行：检查右孩子。右孩子下标是 child + 1（也就是 2i+1），两个条件缺一不可：第一，右孩子在堆内（child + 1 ≤ heapSize）；第二，右孩子确实比左孩子大（heap[child+1] > heap[child]）。只有同时满足才把 child 改成右孩子。注意条件顺序：必须先判越界再取值，否则可能读到废墟区的脏数据。

第 5 行：比较父亲和选中的孩子。父亲 ≥ 孩子，则这一对父子合法。为什么可以放心 break？和上浮同样的道理：父亲以上没动过，本就合法；当前这一层也合法了，下面的子树还是原来合法的子树（交换没有发生），所以整棵子树恢复合法。注意这里用的是 ≥，相等时不动，保持稳定。

第 6 行：父子交换。把”小个子”父亲换下去，把”大孩子”换上来。

第 7 行：i 更新为孩子的下标，循环继续向下检查。每轮 i 至少翻倍（i → 2i），所以最多走树高那么多次。

5.4 下沉与上浮的对称之美

把两个操作并排看，会发现它们是对称的：上浮是”新元素从底部向根走，每次只和父亲比，比不过就换，直到比得过或到根”；下沉是”被贬值的元素从根向叶子走，每次在两个孩子里挑大的比，比不过就换，直到没有孩子或比得过”。一个向上、一个向下，一个”往上比一个”、一个”往下比两个”，共同构成了堆的全部”自愈”能力。

还有一个重要的实现选择：当堆顶被删除后，我们为什么选”最后一个元素”顶上去，而不是随便找一个孩子顶上去？ 因为完全二叉树的形状是全局约束，只有最后一个元素被挪走，才能让”删除一个节点后仍保持连续编号”。如果你把某个中间节点提走，后面所有编号都要左移，形状纪律就毁了。最后一个元素顶上去，牺牲的只是”它可能很小”这个临时问题，而这个临时问题正好交给下沉去解决。用一次下沉的 O(log n)，换来形状的 O(1) 维护，这笔买卖非常划算。

6 插入与删除堆顶：完整流程与复杂度

6.1 插入完整流程

对应代码（完整的小顶堆/大顶堆类骨架，先看插入部分）：

class MaxHeap {
  private heap: number[];
  private size = 0;

  constructor(capacity = 16) {
    this.heap = new Array(capacity + 1);  // 下标 0 不用，多开一格
  }

  insert(x: number): void {
    if (this.size + 1 >= this.heap.length) this.grow();
    this.size++;
    this.heap[this.size] = x;
    siftUp(this.heap, this.size);
  }

  private grow(): void {
    const bigger = new Array(this.heap.length * 2);
    for (let i = 1; i <= this.size; i++) bigger[i] = this.heap[i];
    this.heap = bigger;
  }
}

三个细节值得注意。第一，扩容：动态数组的惯用策略是”容量翻倍”，均摊下来每次插入还是 O(1) 的搬运成本（因为扩容不常发生），所以插入的整体均摊复杂度仍是 O(log n)。第二，下标 0 空着：new Array(capacity + 1) 多开一个格子，让 1 基下标永远不越界。第三，先放后调：先保证结构（放进末尾），再修复秩序（上浮），两步次序绝不能颠倒。

6.2 删除堆顶（poll）完整流程

对应代码：

peek(): number | null {
  return this.size === 0 ? null : this.heap[1];  // 只看不删，O(1)
}

poll(): number | null {
  if (this.size === 0) return null;
  const top = this.heap[1];
  this.heap[1] = this.heap[this.size];
  this.size--;
  if (this.size > 0) siftDown(this.heap, 1, this.size);
  return top;
}

逐行解释 poll：

第一行，空堆检查。size 为 0 时没有东西可删，返回 null（工程上也可以抛异常，看你的 API 约定）。

第二行，保存答案。大顶堆的根就是最大值，先把它抄进 top。

第三行，最后一个元素搬家。a[1] = a[size]，把末尾的元素提到根。注意这里没有真的把 a[size] 清空，它成为”废墟”的一部分，反正 heapSize 已经缩小，谁也不会再读它。

第四行，堆大小减一。这一步让被删的值正式离开堆的逻辑范围。

第五行，条件下沉。如果删完后堆里还有元素，根上那个”小个子”就需要下沉修复秩序。如果堆已空（size 变成 0），下沉会访问 a[1] 之外的内存吗？不会——我们直接跳过，避免边界事故。

第六行，返回答案。

用一个具体例子把 poll 再走一遍，确认每一步都落在实处。假设大顶堆是 [50, 30, 40, 25, 20, 10]（1 基下标），执行 poll()：

第一步，保存答案 top = 50。 第二步，a[1] = a[6]，也就是把 10 搬到根，数组暂时是 [10, 30, 40, 25, 20, 10]，但 heapSize 从 6 变成 5，逻辑上末尾那个 10 已经不属于堆。 第三步，size = 5 > 0，调用 siftDown(1, 5)。根 10 的两个孩子是 30（2 号）和 40（3 号），较大的孩子是 40，10 < 40，交换，数组变成 [40, 30, 10, 25, 20]（只关心前 5 格）。 第四步，10 现在在 3 号位，它的左孩子是 6 号，但 6 > heapSize = 5，没有孩子，下沉结束。 第五步，返回 50。最终堆 [40, 30, 10, 25, 20]：40 ≥ 30、40 ≥ 10、30 ≥ 25、30 ≥ 20，全部合法。

注意第三步的一个细节：比较的是”较大的孩子”。如果当初傻乎乎地和左孩子 30 交换，堆会变成 [30, 10, 40, 25, 20]，根 30 比右孩子 40 小，依旧违规，还得再折腾一轮；和较大的孩子换，一次交换就能让”根与两个孩子”的关系同时合法。这个”挑大的比”的动作，是下沉和上浮最大的不同，也是下沉代码里最容易写错的地方。

还有一个值得记住的观察：poll 之后数组末尾的旧值（本例的 50）其实还在内存里，只是 heapSize 不再覆盖它。如果堆里存的是对象引用，正确的做法是 a[size+1] = null，否则这个”僵尸引用”会阻止垃圾回收，造成内存泄漏。逻辑删除和物理清理是两件事，工程实现里都要做。

6.3 复杂度总览

取堆顶 peek：O(1)——读 a[1] 而已。 插入 insert：O(log n)——放末尾 O(1)，上浮最多走树高 O(log n)。 删除堆顶 poll：O(log n)——搬家 O(1)，下沉最多走树高 O(log n)。 空间：O(n)——一个数组，不含额外的大结构。

关键认知：插入和删除的最坏情况就是 O(log n)，没有任何输入能让它退化。 因为完全二叉树的高度只由节点数量决定，与数据的排列顺序无关——数据再”刁钻”，树高也压不下去；这正是堆比 BST 稳健的根本原因。别忘了，BST 的 O(log n) 是”平均”，堆的 O(log n) 是”保证”。

6.4 边界情况：把最容易翻车的地方一次说清

写完堆代码，测试时一定要先打这四张”边界牌”：空堆、单元素堆、重复值、大堆扩容。每一张牌都是一个真实的 bug 现场。

空堆。 对空堆调用 peek 或 poll，你的实现必须给出明确的行为：返回 null、抛异常，或者调用方约定好的特殊值。很多初学者在 poll 里忘记检查 size === 0，直接读 a[1]，读到的是未初始化的垃圾值，然后在错误的数据上继续下沉，越陷越深。另外，空堆插入第一个元素时要确保不会走到”上浮”的邪路上：i = 1，循环条件 i > 1 直接为假，天然安全。

单元素堆。 size = 1 时，插入一个更小的元素：新元素在 2 号位，上浮一次和根比较，交换或不交换，结束。poll 唯一的元素：top 保存 a[1]，把 a[1] = a[1]（自己抄自己），size 变成 0，此时必须跳过下沉——如果傻傻调用 siftDown(heap, 1, 0)，循环条件 2*1 ≤ 0 为假，其实也不会出事；但养成”size > 0 才下沉”的习惯，代码意图更清楚。

重复值。 堆允许重复元素，这没什么可说的；要小心的是比较符号。上浮用 heap[p] >= heap[i] 停住、下沉用 heap[i] >= heap[child] 停住，相等的值就不交换。如果你手滑写成严格大于/小于，相等的元素会不停交换，虽然最终堆仍然合法，但白白浪费 O(log n) 时间，还会让堆排序的（本来就不存在的）稳定性更差。

扩容。 动态数组翻倍扩容时，最隐蔽的 bug 是”只复制了 length 个格子却没复制满”或者反过来”复制越界”。我们约定下标 0 不用，所以新数组长度 = 旧长度 × 2，但复制循环只走到 size（而不是 length），把废墟区的旧值留在原地不管。别忘了，扩容后 heapSize 没有变，变的只是物理容量——逻辑边界和物理边界的区别，在这里再次显现。

哨兵值（可选优化）。 下标 0 空着不用，其实是浪费了一个格子。有些实现会在 a[0] 放一个”哨兵”：大顶堆放一个正无穷，让所有元素上浮到 i=1 时必然在 0 号位停下（因为任何值都”不大于”正无穷），这样循环条件可以省掉 i > 1 的判断，代码更紧凑。小顶堆则放负无穷。这是性能优化的经典技巧，但可读性略差，面试里先写清楚版本，再提哨兵优化，印象分会更好。

6.5 一个完整的可运行实现

把前面的代码拼起来，就是一份最小的、可运行的 TypeScript 大顶堆。建议你把它敲一遍，然后亲手跑通”插入 8 个乱序数字、连续 poll 全部弹出来”的验证脚本：

class MaxHeap {
  private heap: number[];
  private size = 0;

  constructor(capacity = 16) {
    this.heap = new Array(capacity + 1); // 下标 0 空着
  }

  isEmpty(): boolean { return this.size === 0; }

  peek(): number | null {
    return this.size === 0 ? null : this.heap[1];
  }

  insert(x: number): void {
    if (this.size + 1 >= this.heap.length) this.grow();
    this.size++;
    this.heap[this.size] = x;
    this.siftUp(this.size);
  }

  poll(): number | null {
    if (this.size === 0) return null;
    const top = this.heap[1];
    this.heap[1] = this.heap[this.size];
    this.size--;
    if (this.size > 0) this.siftDown(1);
    return top;
  }

  private siftUp(i: number): void {
    while (i > 1) {
      const p = Math.floor(i / 2);
      if (this.heap[p] >= this.heap[i]) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  private siftDown(i: number): void {
    while (2 * i <= this.size) {
      let child = 2 * i;
      if (child + 1 <= this.size && this.heap[child + 1] > this.heap[child]) {
        child++;
      }
      if (this.heap[i] >= this.heap[child]) break;
      [this.heap[i], this.heap[child]] = [this.heap[child], this.heap[i]];
      i = child;
    }
  }

  private grow(): void {
    const bigger = new Array(this.heap.length * 2);
    for (let i = 1; i <= this.size; i++) bigger[i] = this.heap[i];
    this.heap = bigger;
  }
}

这份代码把上浮、下沉写成了类的私有方法，好处是 heapSize 不再作为参数传来传去，边界直接读 this.size，签名更干净。你完全可以把 siftUp/siftDown 写成自由函数（像前面那样显式传 heapSize），两种风格等价，选一种坚持下去即可。

7 建堆：把任意数组变成堆

7.1 一个朴素但不够好的思路

假设你手里已经有一个长度为 n 的数组，想把它变成大顶堆。最直觉的做法是”逐个插入”：从空堆开始，把数组里的元素一个接一个 insert。n 次插入，每次 O(log n)，总时间 O(n log n)。这个做法没错，但堆的爱好者会告诉你：有更快的办法，只需要 O(n)。

为什么可以更快？关键在于：插入是”自底向上的上浮”，而建堆可以”自顶向下的下沉”，两者路径相反，总成本天差地别。更具体地说，插入时每个元素都可能从自己的位置一路浮到根，叶子数量约占总节点数的一半，如果让一半元素都走到根，代价自然高；而建堆时我们从底部开始整理，每个节点只下沉它实际需要走的距离，叶子根本不用动——它们没有孩子，下沉量为零。

7.2 从最后一个非叶节点开始

建堆算法只有一句话：从最后一个非叶子节点开始，从右往左、从下往上，对每个节点执行一次 siftDown。

最后一个非叶子节点是谁？叶子节点的下标都大于 ⌊n/2⌋（因为下标 > n/2 的节点没有孩子），所以最后一个非叶子节点就是 ⌊n/2⌋。例如 n = 10，最后一个非叶节点是 5；n = 7，最后一个是 3；n = 1，没有非叶节点，建堆什么都不用做。验证一下 n = 10 的完全二叉树：节点 5 的孩子是 10 和 11，11 越界，所以 5 只有左孩子 10；节点 6 到 10 都没有孩子，全是叶子。⌊10/2⌋ = 5，恰好是”最后一个有孩子的节点”。

为什么从下往上？因为 siftDown 有一个隐含前提：被下沉节点的两个孩子都已经是合法的堆。只有先处理完下一层，上一层下沉时才不会把”还没修好的子树”当成熟练工。从 ⌊n/2⌋ 一路倒着走到 1，正好保证处理 i 时，它的左、右子树都已经各是一个合法的堆。

下面用一个 10 个元素的例子完整走一遍。初始数组：[9, 5, 8, 2, 3, 7, 6, 1, 4, 0]（1 基下标，0 号空着），对应这棵树：

第 1 轮：处理 i = 5（值 3）。 它的左孩子是 10 号（0），右孩子越界。较大的孩子是 0，但父亲 3 ≥ 0，合法，不用动。

第 2 轮：处理 i = 4（值 2）。 左孩子 8 号（1），右孩子 9 号（4）。较大的孩子是 4（9 号），2 < 4，交换：

4 下沉到 9 号后没有孩子，结束。

第 3 轮：处理 i = 3（值 8）。 左孩子 6 号（7），右孩子 7 号（6）。较大孩子 7，8 ≥ 7，合法，不用动。

第 4 轮：处理 i = 2（值 5）。 左孩子 4 号（4），右孩子 5 号（3）。较大孩子 4，5 ≥ 4，合法，不用动。

第 5 轮：处理 i = 1（值 9）。 左孩子 2 号（5），右孩子 3 号（8）。较大孩子 8，9 ≥ 8，合法，不用动。

咦，这个例子太”幸运”了，几乎没怎么交换。为了展示下沉真正干活的场景，我们换一个”倒序”的坏例子：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]：

从 i = 5（值 5）开始：左孩子 10（10），5 < 10，交换，5 沉到 10 号位。然后 i = 4（值 4）：左孩子 8（8）、右孩子 9（9），较大是 9，4 < 9，交换到 9 号位。i = 3（值 3）：左 6（6）、右 7（7），较大 7，交换到 7 号位。i = 2（值 2）：左 4（4）、右 5（5），较大 5，交换到 5 号位；到了 5 号位后它还有左孩子 10（10），2 < 10，再交换到 10 号位。i = 1（值 1）：左 2（2）、右 3（3），较大 3，交换到 3 号位；在 3 号位又发现左 6（6）、右 7（7），较大 7，继续交换；到 7 号位后没有孩子，停下。最终数组变成 [10, 5, 7, 9, 2, 6, 3, 8, 4, 1]，这就是一个合法的大顶堆。注意看：最大值 10 浮到了根，但第二层只有 5 和 7，第三层却有 9——堆只保证父子关系，不保证”上层一定大于下层”，9 比 5 大并不违规。

7.3 建堆代码

function buildMaxHeap(arr: number[]): number[] {
  // 约定：调用方传入的 arr 是 1 基（下标 0 不用），就地改造
  const n = arr.length - 1;              // 堆大小 = 真实元素个数
  for (let i = Math.floor(n / 2); i >= 1; i--) {
    siftDown(arr, i, n);
  }
  return arr;
}

代码短到不用逐行讲：n 是堆大小，循环从 ⌊n/2⌋ 递减到 1，每个节点下沉一次。值得注意的只有两点：第一，叶子不用处理，所以起点是 ⌊n/2⌋ 而不是 n；第二，siftDown 的第三个参数必须传 n（而不是 arr.length），因为数组里可能还有没用的 0 号位，而 heapSize 才是逻辑边界。

7.4 为什么建堆是 O(n) 而不是 O(n log n)

这是本篇最重要的复杂度证明之一，值得用一个”直觉 + 算账”的组合拳讲透。

直觉：完全二叉树里，越靠近底部的节点越多，但它们能下沉的距离越短；越靠近顶部的节点越少，但它们能下沉的距离越长。这两种效应正好相互抵消。具体来说，第 h 层（从根往下数，根的深度是 0）有大约 n/2^(h+1) 个节点，每个节点最多下沉 h 次。总工作量大约是：

总下沉次数 ≈ n/2 × 1 + n/4 × 2 + n/8 × 3 + n/16 × 4 + …

这是一个”等比 × 等差”的级数。把 n 提出来：n × (1/2 + 2/4 + 3/8 + 4/16 + …)。括号里的无穷级数收敛于一个常数 2（这是高中数学里的经典结论：k/2^k 从 k=1 到无穷求和等于 2）。所以总工作量 ≈ 2n，也就是 O(n)。

而”逐个插入”为什么是 O(n log n)？插入时每个元素都可能上浮到根附近，越多的元素离根越远，恰好它们付出的代价越大——每个元素 O(log n)，n 个元素乘起来就是 O(n log n)。同样一批叶子，建堆时它们几乎不花钱（没有孩子，下沉为 0），插入时却可能每个人都爬到顶。方向选反了，代价就从”每层分摊”变成了”每人全价”。

再补一句直觉：“底层节点多”为什么不是坏消息？因为它们下沉一次就可能到叶子，几乎不用继续。第 3 篇我们算过，完全二叉树大约一半节点是叶子，四分之一是”只有一层孩子”的节点，八分之一是”有两层孩子”的节点……越往上，节点越少。把”节点数 × 下沉距离”逐层加起来，正好是个收敛级数。这也是建堆算法最反直觉、也最优雅的地方：看起来每个节点都要处理，但大部分节点只需要处理不到一次。

7.5 用手算验证 O(n)：一张分层账本

光说”级数收敛”太抽象，我们拿 n = 15 的完全二叉树亲手算一笔账。15 个节点的完全二叉树正好是满的：第 0 层（根）1 个节点，第 1 层 2 个，第 2 层 4 个，第 3 层 8 个。建堆时叶子（第 3 层）根本不用下沉，我们从第 2 层开始算。

层（从根数起）	节点数	每个节点最多下沉次数	该层总下沉次数
第 2 层	4	1	4 × 1 = 4
第 1 层	2	2	2 × 2 = 4
第 0 层（根）	1	3	1 × 3 = 3
合计	7 个非叶节点	—	11 次

15 个节点建堆，最坏总共下沉 11 次，而 15 × log₂15 ≈ 15 × 3.9 ≈ 58——差了 5 倍多。n = 15 太小看不出”O(n) 对 O(n log n)“的本质区别，把 n 放大到 2^k - 1 个节点的满树，账本变成这样：

层	节点数	每节点下沉次数	该层贡献
第 k-1 层	2^(k-2)	1	2^(k-2)
第 k-2 层	2^(k-3)	2	2^(k-2)
…	…	…	…
第 1 层	2	k-2	2(k-2)
第 0 层	1	k-1	k-1

有趣的事情发生了：把每一层的贡献列出来——第 k-1 层贡献 2^(k-2) × 1 = 2^(k-2)；第 k-2 层贡献 2^(k-3) × 2 = 2^(k-2)；第 k-3 层贡献 2^(k-4) × 3 = 0.75 × 2^(k-2)；第 k-4 层贡献 2^(k-5) × 4 = 0.5 × 2^(k-2)……越往上层，每层贡献越小：虽然单个节点下沉得更远，但节点数按 2 的幂衰减，两者相乘后贡献不升反降。把所有这些项加起来，总和不超过最底层贡献的常数倍，严格推导得到的上界是 2n。换句话说，建堆的总工作量主要由靠近叶子的一两层决定，上层节点虽然”走得远”，但人数太少，总贡献可以忽略。

把公式写严谨一点。设节点总数为 n，第 d 层（从根往下，根的 d = 0）有大约 n/2^(d+1) 个节点，每个节点最多下沉 k-1-d 次（k 是树高），总次数 T(n) = Σ [n/2^(d+1)] × (k-1-d)。这个和可以分成两部分：底层（d 接近 k）项数多但距离短，顶层（d 小）距离长但项数呈指数衰减。用”级数换元”的方法可以严格证明 T(n) ≤ 2n，这也是算法教材里”build-heap 是线性的”标准证明。你不需要背证明过程，但请记住那个直觉：每个节点支付的是”它到叶子的距离”，而不是”它到根的距离”；建堆从下往上，恰好让大部分节点只付一两层的距离。

顺便回答一个高频疑问：“既然建堆是 O(n)，为什么用 insert 逐个建堆却是 O(n log n)？“因为逐个插入是从上往下地”上浮”：每个新元素支付的路径长度是”从插入位置到根的距离”，而大部分插入位置在底部，底部到根的距离接近满树高 k，n 个元素平均每人约 k 次，合计 O(nk) = O(n log n)。同样是那批节点，方向反了，账单就从”每层递减”变成”每人全价”。这是理解建堆复杂度最核心的一句话。

8 堆排序：把堆变成排序器

8.1 算法思路

既然大顶堆的根永远是最大值，一个自然的排序方案就浮出水面了：

第一步（建堆）：把数组建成大顶堆，O(n)。 第二步（反复取最大）：把根（最大值）和最后一个元素交换，让最大值”退休”到数组末尾；然后把堆大小减一（退休区不再参与）；最后对新的根执行一次 siftDown，修复堆序。 第三步（重复 n-1 次）：每次堆大小减一，直到堆里只剩一个元素，数组从小到大排好。

用刚才的堆 [10, 5, 7, 9, 2, 6, 3, 8, 4, 1] 走一遍开头。第 1 次交换：根 10 和末尾 1 换，10 退休到 a[10]，heapSize 变 9，然后对根 1 下沉。下沉过程中 1 一路被 9、8、4 压下去……我们画前两步：

第 2 次交换：新堆顶 9 和当前末尾（下标 9 的 4）交换，9 退休到 a[9]，堆大小变 8，再下沉修复。如此往复，数组的尾部从右往左依次被填上 10、9、8、7、6、5、4、3、2、1——降序输出，升序落盘。为什么”取最大”却得到升序？因为最大值被放在数组的最末尾，次大放在倒数第二……最小的留在最前面，整个数组自然就是从小到大。如果你用小顶堆做同样的事，会得到降序数组。

8.2 完整代码

function heapSort(arr: number[]): number[] {
  const n = arr.length - 1;              // 1 基下标，a[0] 不用
  buildMaxHeap(arr);                     // 第 1 步：建堆 O(n)
  for (let end = n; end >= 2; end--) {   // 第 2 步：反复收编最大值
    [arr[1], arr[end]] = [arr[end], arr[1]]; // 堆顶与末尾交换
    siftDown(arr, 1, end - 1);           // 修复剩下的堆
  }
  return arr;
}

第 1 步建堆：O(n)。第 2 步循环 n-1 次，每次交换 O(1)、下沉 O(log n)，共 O(n log n)。所以堆排序总时间复杂度是 O(n log n)，且最坏、平均、最好都是 O(n log n)——不存在”运气好就快、运气差就慢”的说法。

8.3 稳定性与原地性

原地性（in-place）：堆排序是原地排序，它只在一个数组里通过交换完成，额外空间 O(1)（不计递归栈）。这一点它和快速排序平起平坐，比归并排序更省内存。

稳定性（stable）：堆排序是不稳定排序。原因是交换太”远”：堆顶和末尾相隔千里，两个相等的元素可能一个在堆顶、一个在末尾，一次交换就把它们的相对顺序打乱；而且下沉过程会让元素长距离跳来跳去，根本无法保证”相等的元素保持原顺序”。如果要稳定，得付出 O(n) 额外空间的代价，那就失去堆排序的意义了。

局部性：堆排序的缓存表现一般。它访问的下标是 1、2i、2i+1……虽然是连续数组，但下沉时跨度是 2 倍递增，等于在数组里”跳着走”，CPU 缓存命中率不如顺序扫描的归并排序。这是堆排序在实际中常输给快速排序、归并排序的原因之一。

8.4 与快排、归并的对比表

维度	堆排序	快速排序	归并排序
平均时间	O(n log n)	O(n log n)	O(n log n)
最坏时间	O(n log n)	O(n²)（退化，但可随机化规避）	O(n log n)
额外空间	O(1)	O(log n)（递归栈）	O(n)
稳定性	不稳定	不稳定	稳定
缓存友好度	一般（跳着访问）	好（顺序分区）	好（顺序合并）
优势场景	空间受限、要求最坏有保证	通用场景的默认选择	链表排序、稳定性要求高

一句话选型建议：普通内存排序选快排（或语言内置排序），稳定性优先选归并，既要求最坏 O(n log n) 又要求 O(1) 额外空间时，堆排序才是主角。

另外提一个重要的”降级用法”：堆排序的前 k 步可以直接用来求 Top-K。只要建好堆，交换一次就”收获”一个最大值，做 k 次交换就能拿到最大的 k 个（它们会依次落到数组尾部）。后面第 9 章会给出更常用的 Top-K 方案，这里先留一个印象。

8.5 工程真相：为什么内置排序库几乎不用堆排序

既然堆排序最坏 O(n log n) 且原地，为什么 C 的 qsort、Java 的 Arrays.sort、Python 的 Timsort 都没有选择它？答案藏在三个工程细节里。

第一，缓存与内存访问模式。堆排序的下沉访问下标 1、2、4、8……每一步跨距翻倍，等于在一个大数组里”跳着读”。现代 CPU 依赖缓存行连续预取，堆排序的跳跃访问让缓存频繁失效；快排和归并则是分块、顺序地扫描，缓存命中率高得多。在千万级数据上，缓存效应可以抹平理论复杂度上看似不大的差距。

第二，比较次数偏多。堆排序的理论比较次数约为 2n log n 量级，常数比快排大。快排的常数小、分支简单，实际运行往往更快；加上”数组已接近有序”时快排还有各种优化（如插入排序收尾、三数取中），而堆排序对任何输入都一视同仁地慢吞吞。

第三，不稳定且无法利用已有顺序。堆排序看不出”数组大部分已有序”这件事，无论输入多规整，它都要完整地建堆、完整地交换。Timsort 这类自适应排序会在”基本有序”的输入上跑出 O(n)，堆排序永远做不到。

那堆排序还有用武之地吗？有，而且很明确：内存极度受限、且要求最坏情况有严格保证的场景，比如嵌入式系统、实时系统、部分数据库的磁盘外部排序辅助结构。它还是算法竞赛里”写不出快排稳定版本时的兜底方案”。工程结论一句话：堆排序是”理论满分、工程及格”的选手，它最重要的价值是教会我们堆，而不是取代快排。

9 优先队列应用：从算法题到操作系统

堆的威力不在定义里，而在应用中。这一章我们一口气看五个经典场景：海量数据 Top-K、合并 K 个有序链表、任务调度、Dijkstra 最短路、中位数维护。每一个场景都对应一类真实的工程需求，也几乎是面试里”优先队列”考点的全部题库。

9.1 应用一：海量数据 Top-K

问题：一个包含 10 亿个数字的文件，内存装不下全部数据，怎么找出最大的 100 个？

错误答案：全部排序。10 亿个数排序至少要读一遍 + 大量比较，而且数据根本装不进内存。

正确答案：维护一个大小为 100 的小顶堆。小顶堆的根是堆里最小的，也就是”当前前 100 名里最弱的那一个”。具体流程：

1. 先读前 100 个数，建一个小顶堆。
2. 继续读后面的每个数 x：如果 x 比堆顶（当前第 100 名）还小，说明 x 连前 100 都进不了，直接丢弃；如果 x 比堆顶大，就把堆顶踢出去（poll），把 x 插进去（insert）。
3. 文件读完后，堆里的 100 个数就是全局最大的 100 个。

为什么用小顶堆而不是大顶堆？大顶堆的根是堆内最大，用它无法回答”新来的 x 够不够资格进前 100”——你总不能每次都和最大的比，比赢了还得删最大，逻辑全拧了。小顶堆的根是”守门员”：它是最弱的前 100 名成员，任何新人都只要打败守门员就能入队。这个”让弱者守门”的视角，是 Top-K 问题的灵魂。

复杂度：每个数一次 O(log k) 的比较和可能的插入，总共 O(n log k)。n 是 10 亿，k 是 100，log k 只是 7 次左右的比较，快得惊人；空间只要 O(k)，完全无视海量数据。如果 k 远小于 n，这个方案比任何排序都快一个数量级。

对称地，求”最小的 100 个”就维护大小为 k 的大顶堆，让”最大的弱者”守门。

9.2 应用二：合并 K 个有序链表

问题：有 K 个已经各自排好序的链表（比如 K 个日志文件、K 个归并段），要把它们合并成一个整体有序的链表。

朴素思路：K 个链表各有一个指针，每轮扫描 K 个指针找最小值，取走一个。总共有 n 个元素，每轮 O(K)，总时间 O(nK)。K 是 1000 时，慢得离谱。

堆思路：把 K 个链表的当前头节点全部丢进一个小顶堆（按值排序）。堆里最多 K 个元素。每轮：

1. 从堆里 poll 出最小的节点，接到答案链表尾部。
2. 这个节点在原链表里的下一个节点，insert 进堆。
3. 堆空时结束。

每轮 poll + insert 都是 O(log K)，一共 n 个元素，总时间 O(n log K)，空间 O(K)。对比朴素法 O(nK)，K 越大，堆的优势越恐怖。这也是外部排序里”多路归并”的标准做法——归并排序的”败者树”本质上就是堆的亲戚。

// 伪代码：K 个有序链表的合并
function mergeKLists(lists: ListNode[]): ListNode | null {
  const minHeap = new MinHeap();          // 小顶堆，节点按值比较
  for (const head of lists) {
    if (head) minHeap.insert(head);       // 每个链表的头先入堆
  }
  const dummy = new ListNode(0);
  let tail = dummy;
  while (!minHeap.isEmpty()) {
    const node = minHeap.poll()!;         // 取当前最小
    tail.next = node;                     // 接进答案
    tail = node;
    if (node.next) minHeap.insert(node.next); // 补上它的后继
  }
  return dummy.next;
}

注意一个细节：堆里存的是节点引用而不是值，比较时看 node.val。如果两个节点值相等，谁先出无所谓——堆不稳定也没关系，因为所有相等的节点最终都会按顺序被取出。

9.3 应用三：任务调度

回到文章开头提到的操作系统。一个实时调度器要维护”当前所有可运行的进程”，每次 CPU 空闲时选出优先级最高的一个执行。这正是优先队列的教科书用法：进程创建时 insert，进程结束或阻塞时删除，优先级改变时先删除再插入（或者用索引堆做 decrease-key，见第 10 章）。

除了操作系统，这个模型到处都是：网络服务器按”请求优先级”调度 API 调用、打印机按”页数最少”先打、电商秒杀系统按”会员等级”优先处理订单、游戏引擎按”渲染距离”排序更新实体……凡是”系统里同时有很多任务，但资源一次只能服务一个，且服务顺序由某个优先级决定”的场景，堆就是那个天然的排队器。

工程上还有一个进阶玩法叫定时任务：把每个任务的”下次执行时间”放进小顶堆，每次取堆顶就知道”下一个该触发谁、还要等多久”。操作系统里的定时器、消息队列里的延迟队列，底层常常就是这么一张”时间堆”。

9.4 应用四：Dijkstra 最短路（给图系列埋伏笔）

Dijkstra 算法是求”带权图中，从起点到所有其他点的最短距离”的经典算法，也是堆在算法竞赛和面试里最重要的应用之一。它的核心循环是：

1. 从”未确定最短路的节点”里，选出当前距离最小的那个（记为 u）。
2. 用 u 去松弛它的所有邻居：如果”起点到 u 的距离 + u 到邻居的边权”比之前记录的更小，就更新邻居的距离。
3. 重复直到所有节点确定。

第 1 步”每次找距离最小的节点”——这就是一个优先队列的需求！把”（节点，当前距离）“丢进小顶堆，每次 poll 出距离最小的；发现更短距离时，往堆里再插入一个新记录。堆让”找最小”从 O(n) 扫描降到 O(log n)，整个算法从 O(n²) 优化到 O((n + m) log n)，其中 m 是边数。图越大、边越多，优势越明显。

细心的读者会问：更新距离时为什么是”插一条新记录”而不是”修改堆里旧记录”？因为普通堆不支持按节点查找和修改，只能”旧记录留着不管，新记录插进去”；poll 时如果发现”这条记录的距离比节点当前已知距离大”，说明它是过期的，直接丢弃。这个”懒惰删除（lazy deletion）“的技巧让 Dijkstra 可以只用最普通的堆实现。等图系列讲到最短路时，我们会把这个算法的每一步展开；今天你只需要记住：Dijkstra 的加速器就是堆，这是堆最有含金量的应用，没有之一。

9.5 应用五：中位数维护（双堆）

问题：数据流源源不断到达，随时要求”当前所有数的中位数”，插入和查询都要快。

思路：用两个堆——一个大顶堆 maxHeap 存较小的一半，一个小顶堆 minHeap 存较大的一半，并且保证”小的一半最多比大的一半多一个元素”。那么：

• 中位数 = maxHeap 的根（如果总数是奇数）；
• 中位数 = (maxHeap 根 + minHeap 根) / 2（如果总数是偶数）。

插入新数 x 时，先和 maxHeap 的根比较决定进哪个堆，然后平衡两边数量：如果某一堆比另一堆多出 2 个，就把它的根搬到对面。每次插入最多一次 poll + 一次 insert，O(log n)；查询中位数 O(1)。这套”一大一小双堆”的组合，是数据流中位数问题的标准答案，也是”堆可以当半个平衡树用”的最好证明。

class MedianFinder {
  private lo = new MaxHeap();  // 较小的一半（大顶堆）
  private hi = new MinHeap();  // 较大的一半（小顶堆）

  addNum(x: number): void {
    if (this.lo.isEmpty() || x <= this.lo.peek()!) {
      this.lo.insert(x);
    } else {
      this.hi.insert(x);
    }
    // 平衡：lo 最多比 hi 多 1 个；hi 绝不能比 lo 多
    if (this.lo.size() > this.hi.size() + 1) {
      this.hi.insert(this.lo.poll()!);
    } else if (this.hi.size() > this.lo.size()) {
      this.lo.insert(this.hi.poll()!);
    }
  }

  findMedian(): number {
    if (this.lo.size() > this.hi.size()) return this.lo.peek()!;
    return (this.lo.peek()! + this.hi.peek()!) / 2;
  }
}

约定里 lo 可以比 hi 多一个，但 hi 不能比 lo 多——这样当总数是奇数时，中位数永远在 lo 的根上。如果你想让中位数”永远偏大一半”，把约定反过来即可。细节不重要，重要的是那个画面：两个堆像天平的两端，一个托住较小的一半，一个托住较大的一半，中位数就挂在两只指针中间。

五个应用讲完，你应该已经感受到：优先队列不是一个”算法题专用”的玩具，而是所有”动态地、反复地、只关心极值”的问题的通用答案。如果你还想亲手”玩一玩”排序和堆的行为，可以在排序实验室里看各种排序算法的可视化过程，堆排序的”反复交换堆顶”在里面一目了然。

9.6 应用六：数据流中的第 K 大元素

Top-K 还有一个”动态版”：数据源源不断到达，随时要回答”当前所有数里第 K 大的是谁”。比如股票价格流里要实时维护”最近的价格里第 K 高”，排行榜里要维护”当前第 K 名”。

做法和静态 Top-K 几乎一样：维护一个恰好 K 个元素的小顶堆，堆顶就是第 K 大。新数 x 到达时：

1. 如果堆里不足 K 个，直接插入；
2. 如果 x ≤ 堆顶，说明 x 连第 K 名都进不了，丢弃；
3. 如果 x > 堆顶，poll 掉堆顶（旧的第 K 大出局），insert(x)，新的堆顶就是新的第 K 大。

class KthLargest {
  private minHeap = new MinHeap();
  private k: number;

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) this.add(x);
  }

  add(x: number): number {
    if (this.minHeap.size() < this.k) {
      this.minHeap.insert(x);
    } else if (x > this.minHeap.peek()!) {
      this.minHeap.poll();
      this.minHeap.insert(x);
    }
    return this.minHeap.peek()!; // 堆顶 = 第 K 大
  }
}

为什么”第 K 大”的答案是”堆里最小”？想清楚这一句，Top-K 全家就通了：堆里保留的是目前最大的 K 个，其中最小的那个（守门员）恰好是”第 K 名”。第 K 大不是”第 K 个从大到小排的值”吗？最大的 K 个里最小的，正好就是它。每次 add 只花 O(log K)，长期运行毫无压力。

9.7 应用七：滑动窗口最大值

问题：给一个数组和一个窗口大小 k，窗口每次向右滑一格，求每个窗口里的最大值。这是单调队列的经典题，但用堆也能做，而且堆的做法能顺便演示一个非常重要的技巧——延迟删除（lazy deletion）。

思路：大顶堆里存”（值, 下标）“对，窗口滑动时：

1. 把新元素 insert 进堆；
2. poll 时，如果堆顶的下标已经滑出窗口（下标 < 当前窗口左边界），说明它是”过期数据”，丢掉再 poll，直到堆顶是窗口内的元素；
3. 窗口内最大值就是堆顶的值。

function maxSlidingWindow(nums: number[], k: number): number[] {
  const heap = new MaxHeap();          // 按 (值, 下标) 比较
  const ans: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    heap.insert([nums[i], i]);         // 新元素入堆
    while (heap.peek()![1] <= i - k) { // 堆顶已滑出窗口？
      heap.poll();                     // 延迟删除：现在才真正清走
    }
    if (i >= k - 1) ans.push(heap.peek()![0]);
  }
  return ans;
}

注意这里的删除时机：元素滑出窗口的那一刻，我们并没有立刻在堆里找它删它（普通堆也做不到按值删），而是让它继续待在堆里当”僵尸”，直到它升到堆顶被我们看到，才顺手清掉。这就是”懒惰”的代价：堆里可能残留 O(n) 个过期元素，所以插入还是 O(log n)，但每次 poll 的循环摊还下来每个元素只被删一次，总复杂度 O(n log n)。延迟删除是一个极其通用的技巧——Dijkstra 的”旧距离记录”、滑动窗口、区间合并，凡是”逻辑上已删除但物理上不好删”的场景，都能用它。

堆解法不是滑动窗口最优解（单调队列是 O(n)），但它是”会堆的人第一反应”的解法，而且展示了堆在动态数据里的弹性。如果面试官要求最优，你再补单调队列；如果要求”给我一个能跑通的思路”，堆解法就是最稳的答案。

9.8 应用八：合并区间与会议室问题（顺带一提）

还有两类高频题，本质也是”排序 + 堆”。合并区间：先按起点排序，再用一个小顶堆（或直接比较当前区间起点与已合并区间终点）判断重叠。会议室问题：给一组会议的开始/结束时间，问最少需要几间会议室——把会议按开始时间排序，用小顶堆维护”正在进行的会议的结束时间”，新会议开始前先弹出所有已结束的会议，然后入堆；堆的最大长度就是所需会议室数量。这两题堆不是主角，但”按时间线维护活跃集合”的手法和任务调度一模一样，刷题时遇到它们，你就能认出堆的影子。

10 堆的变体：三张”升级牌”

基础堆已经很强，但工程师永远想要更快、更灵活。这一章介绍三个著名变体，每一个都对应基础堆的一个”短板”。我们只说清”它解决什么问题、为什么值得知道”，不展开实现细节——它们值得在之后的专题里单独细讲。

10.1 d 叉堆：降低树高

普通二叉堆的每个节点最多 2 个孩子，所以树高 O(log₂ n)。**d 叉堆（d-ary heap）**允许每个节点最多 d 个孩子，树高降到 O(log_d n)。孩子下标公式从”2i、2i+1”变成”di-(d-2)、di-(d-1)、……、di+1”这种连续区间的形式，数组存储依然成立。

d 越大，树越矮，下沉需要的比较轮数越少；但每轮要比较的孩子变多（找最大/最小孩子要扫 d 个），插入的上浮每轮仍然只比一个父亲，所以插入变快、删除变慢。工程上 d 取 3 到 5 时往往有不错的实测表现。d 叉堆还告诉我们一个普适规律：数据结构永远在”比较的次数 × 比较的轮数”之间做交易，没有免费的午餐。

10.2 索引堆：支持 decrease-key

普通堆有个尴尬的限制：它只认值，不认身份。你想修改堆里某个特定元素（比如 Dijkstra 里把节点 v 的距离改小），普通堆得先 O(n) 扫描找到它，再上浮，而且扫描过程中还分不清”哪个 5 是你要的 5”。**索引堆（indexed heap）**解决这个问题：堆里不存值本身，而是存”元素的下标”，另外用一个数组 value[i] 存第 i 个元素的值，再用一个位置数组 pos[i] 记录”元素 i 现在住在堆的哪个格子里”。

有了 pos 表，decrease-key(i, newValue) 就是 O(log n)：把 value[i] 改小，然后根据 pos[i] 找到它在堆里的位置，直接上浮。这正是 Dijkstra 优化的另一个经典版本——用索引堆替代”懒惰删除”，堆里的记录数从 O(m) 压回 O(n)。图论、网络流算法里，索引堆是常见的基本功。

10.3 斐波那契堆：把”摊还”玩到极致

斐波那契堆（Fibonacci heap）是堆家族里的”理论天花板”：它把插入和 decrease-key 做到了摊还 O(1)，删除堆顶摊还 O(log n)。它靠的不是一棵完整的树，而是一组”懒散”的树：允许堆里有多棵树（森林），insert 只是把新节点挂上去，几乎不干活；decrease-key 也只是把节点”剪”下来挂到根表，顺便调整一下标记；真正的整理工作攒到 poll 时才统一爆发。

为什么值得知道它？因为在图算法里，如果边很多而 decrease-key 很频繁，斐波那契堆可以把 Dijkstra 从 O((n+m) log n) 再优化到 O(n log n + m)——虽然常数很大、工程实现复杂，导致实际库里很少用它，但它是理解”摊还分析”和”懒惰数据结构”的最佳教材。面试中你只需要知道三句话：插入摊还 O(1)，decrease-key 摊还 O(1)，删除最小摊还 O(log n)，它是为图算法而生的理论利器。

10.4 主流语言里的堆：拿来就能用

大部分现代语言都内置了堆或优先队列，写业务代码时不用自己实现。但它们有各自的脾气，用之前先认清：

Python 的 heapq：标准库模块，只有小顶堆，而且操作的是普通列表。它采用 0 基下标：父是 (i-1)//2，左子是 2i+1，右子是 2i+2。常用函数是 heapq.heappush(heap, x)、heapq.heappop(heap)、heapq.heapify(list)。想要大顶堆？两个技巧：存负数（对数值），或者存 (priority, id) 元组（对对象）。

Java 的 PriorityQueue：默认是小顶堆，用元素的自然顺序或传入的 Comparator 决定优先级。它是”懒扩容 + 自动上浮下沉”的黑盒，插入和删除都是 O(log n)，支持迭代但迭代顺序不保证有序。想要大顶堆：Comparator.reverseOrder() 或 (a,b) -> b-a。Java 还有 TreeSet 可以作为”可删除任意元素”的替代品，但它是红黑树，不是堆。

C++ 的 priority_queue：默认是大顶堆（template 第三个参数传 greater 变最小堆）。它只暴露 top、push、pop，不支持迭代，也不支持删除堆内任意元素；需要”删除任意元素”时，可以配合 unordered_set 记录”已删除”，用延迟删除技巧。

Go 的 container/heap：提供接口让用户自定义堆类型，默认语义也是最小堆；实现 heap.Interface（Len、Less、Swap、Push、Pop）后，heap.Init、heap.Push、heap.Pop 就能工作。它的下标约定同样是 0 基，所以手写 siftUp/siftDown 时要用 (i-1)/2、2i+1、2i+2 那套公式。

JavaScript / TypeScript：标准库没有内置堆。Node.js 生态里有 tinyqueue、heap 等第三方包，但面试和算法练习里通常要求手写，这也正是本文把上浮、下沉讲得这么细的原因。好消息是：堆的全部核心代码不到四十行，手写一次之后，你在任何语言里都能几分钟内把它”翻译”出来。

把这些语言放在一起看，你会发现一个规律：“堆默认是大顶还是小顶”因语言而异（C++ 默认大顶，Python/Java 默认小顶），下标约定也分 1 基和 0 基。所以”读文档确认默认行为”比”背结论”可靠得多。另外，无论哪种语言，堆的 API 都只暴露”取堆顶”，不会让你随机访问中间元素——因为堆的结构决定了”中间元素没有任何可保证的性质”，读了也没用。

11 堆操作复杂度速查表

操作	二叉堆	说明
peek（看堆顶）	O(1)	读 a[1]，无副作用
insert（插入）	O(log n)	放末尾 + 上浮
poll（删堆顶）	O(log n)	末尾搬家 + 下沉
build（建堆）	O(n)	从 ⌊n/2⌋ 向下下沉
heapSort（排序）	O(n log n)	建堆 O(n) + n 次下沉
Top-K（k 远小于 n）	O(n log k)	小顶堆守门员方案
空间	O(n)	一个数组，原地操作

三个必须背下来的数字：peek O(1)，insert/poll O(log n)，build O(n)。如果你只能带走三句话，请带走这三句。

常见陷阱清单（写代码前逐条自检）：

1. 下标从 1 还是 0 开始？ 全文统一，别混用。混用是堆 bug 的第一大来源。
2. heapSize 和数组长度分清了吗？ 孩子是否存在要看 heapSize，不是 array.length。
3. 下沉时比较的是较大的孩子吗？ 大顶堆比”较大孩子”，小顶堆比”较小孩子”，比错一个就全错。
4. 相等时 break 了吗？ 用 ≥ / ≤ 停住，别做无谓交换，稳定性和性能都受益。
5. poll 之后空堆能安全处理吗？ size 为 0 时不要调用下沉。
6. 上浮的循环条件写对了吗？ i > 1 而不是 i >= 1，根没有父亲。
7. 建堆的方向对吗？ 从 ⌊n/2⌋ 往 1 走，不是从 1 往 n 走；叶子不需要下沉。

12 自测题

13 下一篇预告

下一篇是《树系列第 17 篇：Trie——前缀树》。我们已经认识了平衡树（BST、AVL、红黑树）、B 树和堆——它们都在回答”怎么组织一个整体有序（或部分有序）的集合”。但还有一类问题它们都不擅长：字符串的前缀匹配。输入法里打一个”bei”，候选词立刻给出”北京、北漂、背后”；搜索引擎输入”树系列”，下拉框出现”树系列第 15 篇”；手机的通讯录按拼音首字母找人。这些场景的共同点是：我们需要按”前缀”快速找到所有以某段字符开头的字符串。Trie 就是专门为这个需求而生的树：它把字符串的公共前缀合并存储，让”查前缀、统计前缀、排序字符串、补全单词”全部变成沿着树走路的游戏。

第 17 篇里你会看到，Trie 的本质是”用空间换时间”的极致选手：每个节点存 26 个孩子指针（或哈希表），一次前缀查询只需要走字符串那么长的路；你还会看到 Trie 如何轻松解决”单词搜索""字典序排序""最长公共前缀”这些经典问题，以及它和哈希表、BST 在字符串场景下的正面交锋。等 Trie 讲完，“树系列”就只剩最后几块拼图：线段树、树状数组，以及一个把前面所有知识串起来的实战项目。

14 写在最后

回头看看这一篇我们走过的路：从”总是要最大/最小”的日常需求出发，我们排除了数组、链表、BST 三个候选人，认识了由”完全二叉树 + 堆序性质”两条纪律框定的堆；然后我们把树装进数组，用三条下标公式代替全部指针；接着亲手实现上浮和下沉两个核心操作，用它们拼出插入、删除、建堆、堆排序一整条流水线；最后，我们把堆放进 Top-K、多路归并、任务调度、Dijkstra 和双堆中位数的真实战场，并眺望了 d 叉堆、索引堆、斐波那契堆三张升级牌。

如果只让你带走一幅画面，请带走这一幅：堆是一棵”住进数组的完全二叉树”，它用部分有序换来了极端的简单与稳定——取极值 O(1)，插删 O(log n)，建堆 O(n)，而且永远不退化。 如果只让你带走一个方法，请带走”下沉找较大的孩子、上浮只找父亲”这对镜像操作——它们就是堆的全部灵魂。

动手建议三件事：第一，用 TypeScript 自己写一个最小可用的大顶堆（插入、poll、peek），再用随机数据验证”每次 poll 都返回当前最大”；第二，把建堆的 O(n) 证明用手算一个 15 个节点的完全二叉树，把每层的”节点数 × 下沉距离”加一遍，感受级数收敛；第三，用双堆方案写一个 MedianFinder，对着 [3,1,4,2] 一步步验证中位数。三件事做完，堆就会从”读过”变成”长在你手上”。

下一篇，《树系列第 17 篇：Trie——前缀树》，我们换一个赛道，从”数字比大小”转向”字符串找前缀”。第 17 篇见。