特殊的二叉树——堆结构及其在排序中的应用|算法篇
# 前置知识：完全二叉树
30 秒速记
- 完全二叉树除最后一层外都填满，最后一层从左到右连续填充，因此适合用数组紧凑存储
- 零基数组中父结点是
Math.floor((i - 1) / 2)，左右孩子是2i + 1、2i + 2 - 完全性是形状约束，不规定父子值大小；堆还要额外满足堆序性质
完全二叉树除最后一层外都必须填满，最后一层的结点还要从左到右连续排列。 正因为形状紧凑，它可以按从上到下、从左到右的顺序存进数组，不需要额外保存连接关系。零基数组中，索引 i 的父结点是 Math.floor((i - 1) / 2)，左右孩子分别是 2 * i + 1 和 2 * i + 2。这里约束的是树的形状，并没有规定父子结点值的大小。
完全二叉树是指同时满足下面两个条件的二叉树：
- 从第一层到倒数第二层，每一层都是满的，也就是说每一层的结点数都达到了当前层所能达到的最大值
- 最后一层的结点是从左到右连续排列的，不存在跳跃排列的情况（也就是说这一层的所有结点都集中排列在最左边）。
完全二叉树可以是这样的：
也可以是这样的：
但不能是这样的：
更不能是这样的：
注意，完全二叉树中有着这样的索引规律：假如我们从左到右、从上到下依次对完全二叉树中的结点从0开始进行编码：
那么对于索引为 n 的结点来说：
- 索引为
(n-1)/2的结点是它的父结点 - 索引
2*n+1的结点是它的左孩子结点 - 索为引
2*n+2的结点是它的右孩子结点
面试官追问
追问 1可视化页面中一棵树除最后一层外都满，但最后一层节点出现在最右侧、左侧留空，设计师称它仍是完全二叉树，你怎么反驳？
它不是完全二叉树，因为最后一层必须从左到右连续占位，不能在左侧留下空洞后又出现节点。仅满足前面各层为满层还不够；这个反例会破坏按层连续存入数组时的紧凑索引关系。
追问 2堆组件用零基数组保存节点，代码评审要求你写出索引 i 的父节点和两个孩子位置，并说明边界怎么处理？
左孩子是 2*i+1，右孩子是 2*i+2，非根节点的父节点是 Math.floor((i-1)/2)。计算出的孩子下标必须小于数组长度才真实存在，根节点没有父节点；公式成立依赖节点按层且从左到右连续存放。
追问 3批量建堆时同事从数组末尾每个节点都执行下沉，你会把起点改到哪里，依据是什么？
应从最后一个非叶节点 Math.floor(n/2)-1 开始向前下沉，因为零基数组中其后的节点都没有孩子。叶节点天然满足局部堆约束，无需处理；空数组或单元素数组得到负起点时应直接结束。
追问 4序列化模块收到普通二叉树，需要判断它能否紧凑编码为完全二叉树；日志显示某层出现空位后，后续又读到非空节点，你如何判定？
应立即判为非完全二叉树，因为层序扫描一旦遇到首个空孩子，后续位置只能继续为空。实现时可设置“已进入空缺区”标记，之后发现非空节点即失败；若随意跳过空位，就会掩盖中间空洞。
追问 5存储组选型时，一方要用数组保存任意稀疏二叉树，另一方只接受完全二叉树，你会怎样解释空间取舍？
完全二叉树按层连续排列，数组下标即可定位父子，不需要额外指针，也不会因结构产生大量空槽。任意稀疏树若强行沿用同样的位置编码，深层少量节点可能对应很大的下标；此时显式节点引用通常更合适。
# 什么是堆
30 秒速记
- 堆是完全二叉树加父子偏序：最大堆只保证父节点不小于孩子，不保证整棵树有序。
- 数组下标关系：父
(i-1)>>1，左子2i+1，右子2i+2。 - 读堆顶
O(1)，插入与删除堆顶O(log n)，查任意值仍是O(n)。 - 连续数组存储不需要节点指针，缓存局部性好。
堆是一棵满足父子大小约束的完全二叉树，分为大顶堆和小顶堆。 大顶堆要求父节点不小于孩子，小顶堆正好相反，但这不代表同层节点或整棵树全局有序。用数组存储时，父节点下标是 (i-1)>>1，左右孩子分别是 2i+1 和 2i+2。因此读取堆顶是 O(1)，插入和删除堆顶是 O(log n)，查找任意值仍可能需要 O(n)。
堆是完全二叉树的一种特例。根据约束规则的不同，堆又分为两种：
- 大顶堆
- 小顶堆
如果对一棵完全二叉树来说，它每个结点的结点值都不小于其左右孩子的结点值，这样的完全二叉树就叫做“大顶堆”：
若树中每个结点值都不大于其左右孩子的结点值，这样的完全二叉树就叫做“小顶堆”
面试官追问
追问 1排行榜页面拿到数组 [9, 8, 6, 3, 1]，同事看到父节点都更大，就断言任意中序遍历也会降序，你会给出什么判断？
这个断言不成立，大顶堆只保证每个父节点不小于直接孩子，不规定左子树与右子树之间的全序关系。中序遍历次序由树形位置决定，因此不能当作排序结果；要获得全序仍需持续取堆顶并恢复堆。
追问 2任务调度器只关心下一项最高优先级，为什么选择大顶堆而不是维护一个普通无序数组？
大顶堆把当前最大值稳定放在根部，读取下一项时可直接访问堆顶，新增或删除后再沿父子路径恢复约束。无序数组插入简单，但选最大项需要扫描；堆的代价是不能保持全部元素的有序展示。
追问 3产品把“每个父节点都不小于孩子”的规则应用到一棵缺口很多的普通树，并称其为大顶堆，你是否认可？
不认可，堆除了父子大小约束，还要求底层结构是完全二叉树。普通树即使局部大小关系全部成立，也不具备堆的紧凑层序布局；缺口会使基于数组下标计算父子的实现失去前提。
追问 4搜索接口要在百万级大顶堆中按 id 定位任意任务，开发声称能像二叉搜索树一样每次排除一半分支，你会如何纠正？
堆序只能说明父节点与孩子的相对大小，左右分支之间没有可用于二分搜索的全序关系。按任意 id 或普通目标值查找时，最坏仍可能检查大量节点；若定位是核心需求，应增加映射索引或改用更匹配的结构。
追问 5告警显示大顶堆根节点不是全局最大值，但抽查部分父子关系正常，你会优先验证哪些不变量？
应遍历所有有效父节点，检查其值是否都不小于存在的左右孩子，同时确认数组对应的是无空洞的完全二叉树。只抽查一条路径不足以证明堆成立；还要追踪最近的插入或删除是否漏做了上浮、下沉或边界更新。
# 堆的基本操作：以大顶堆为例
30 秒速记
- 大顶堆只保证每个父结点不小于孩子，不保证同层或整个数组全局有序
- 插入先放数组末尾再上浮；删除堆顶用末尾元素补根后下沉，两者时间都是
O(log n) - 下沉必须在左右孩子中选择更大的一个交换，否则可能修好一侧却仍违反另一侧堆序
大顶堆的核心操作是删除堆顶和追加元素，两者本质上都是在恢复父节点不小于孩子的约束。 插入时把新值放到数组末尾，再沿祖先链向上比较和交换；删除时用末尾元素补到根节点，再向下调整。下沉时要从左右孩子中选择更大的那个，否则交换后另一侧仍可能不满足堆序。两种调整最多走一层树高，所以时间复杂度都是 O(log n)。
大顶堆和小顶堆除了约束条件中的大小关系规则完全相反以外，其它方面都保持高度一致。现在我们以大顶堆为例，一起来看看堆结构有哪些玩法。
这里我给出一个现成的大顶堆：
很多时候，为了考察你对完全二叉树索引规律的掌握情况，题目中与堆结构同时出现的，还有它的层序遍历序列：
[9, 8, 6, 3, 1]
我们需要关注的动作有两个：
- 如何取出堆顶元素（删除操作）
- 往堆里追加一个元素（插入操作）
至于堆的初始化，也只不过是从空堆开始，重复执行动作2而已。因此，上面这两个动作就是堆操作的核心。
面试官追问
追问 1优先队列删除大顶堆的根后，代码直接把数组首项移除并让其余元素左移，页面随即读到错误堆顶，问题出在哪？
直接左移会改变几乎所有节点的父子位置，并且不会自动恢复大顶堆约束。通常应把末尾元素移到堆顶、缩短数组，再从根向下与较大的孩子交换；下沉必须持续到父子关系重新满足或到达叶子。
追问 2实时任务进入大顶堆时，新元素被追加到数组末尾，但高优先级任务一直没有升到堆顶，你会怎样补全插入流程？
追加到末尾只维持了完全二叉树形状，还需要将新节点与父节点比较并持续上浮。只要它大于父节点就交换，直到不再违反大顶堆约束或到达根；比较方向写反会构造出小顶堆或局部失序。
追问 3初始化十万级任务堆时，工程师从空数组逐个插入，另一位建议直接对完整数组自底向下下沉，你怎么取舍？
逐个插入语义直观，但每个新节点都可能沿高度上浮，整体上界会达到 O(n log n)。已有完整数组时，从最后一个非叶节点开始依次下沉可做到 O(n) 建堆；若数据本来就是流式到达，则逐项插入仍是自然方案。
追问 4线上删除堆顶后偶发父节点小于右孩子，排查发现下沉时总是优先和左孩子交换，你会如何修复？
大顶堆下沉时应在存在的孩子中选择值更大的一个，再判断是否需要与父节点交换。固定选左孩子可能让父节点交换后仍小于右孩子；还要单独处理只有左孩子的尾部节点，避免越界读取。
追问 5搜索团队要求大顶堆同时支持任意任务按值 O(log n) 删除，但不愿维护额外索引，你会接受这个指标吗？
不能仅凭堆结构保证该指标，因为找到任意目标最坏需要 O(n)，只有定位后的上浮或下沉通常受树高限制。若任务具有唯一 id，可维护 id 到数组下标的映射，并在交换时同步更新；代价是额外空间和一致性维护。
追问 6排序模块想复用大顶堆，每次取出堆顶后把最大值放到数组末尾，这和普通优先队列删除有什么衔接？
两者核心动作相同：交换堆顶与当前有效区末尾，缩小堆的有效范围，再对新根执行下沉。堆排序把移出的最大值保留在数组尾部形成有序区，而优先队列通常直接删除它；实现时必须区分有效堆长度与数组总长度。
# 取出堆顶元素
30 秒速记
- 先保存堆顶，再把数组末元素移到根并缩短堆大小
- 下沉时先比较两个孩子，最大堆必须选择更大的孩子作为交换候选
- 当前值已不小于候选孩子时立即停止，父子偏序已经恢复
- 单元素堆移除后直接为空；一般情况时间
O(log n)、额外空间O(1)
取出大顶堆的堆顶时，要先保存根节点，再用数组末尾元素补到根部并向下调整。 下沉过程中先比较左右孩子，选择值更大的孩子与当前节点比较，因为交换后必须同时满足两侧的父子约束。当前节点已经不小于这个孩子时就可以停止，说明堆序已经恢复。单元素堆删除后直接变为空堆；一般情况下耗时 O(log n)，额外空间为 O(1)。
取出元素本身并不难，难的是如何在删除元素的同时，保持住队的“大顶”结构特性。为了做到这点，我们需要执行以下操作：
- 用堆里的最后一个元素（对应图中的数字1）替换掉堆顶元素。
- 对比新的堆顶元素（1）与其左右孩子的值，如果其中一个孩子大于堆顶元素，则交换两者的位置：
交换后，继续向下对比1与当前左右孩子的值，如果其中一个大于1，则交换两者的位置：
重复这个向下对比+交换的过程，直到无法继续交换为止，我们就得到了一个符合“大顶”原则的新的堆结构：
上述这个反复向下对比+交换的过程，用编码实现如下（仔细看注释）：
// 入参是堆元素在数组里的索引范围，low表示下界，high表示上界
function downHeap(low, high) {
// 初始化 i 为当前结点，j 为当前结点的左孩子
let i=low,j=i*2+1
// 当 j 不超过上界时，重复向下对比+交换的操作
while(j <= high) {
// 如果右孩子比左孩子更大，则用右孩子和根结点比较
if(j+1 <= high && heap[j+1] > heap[j]) {
j = j+1
}
// 若当前结点比孩子结点小，则交换两者的位置，把较大的结点“拱上去”
if(heap[i] < heap[j]) {
// 交换位置
const temp = heap[j]
heap[j] = heap[i]
heap[i] = temp
// i 更新为被交换的孩子结点的索引
i=j
// j 更新为孩子结点的左孩子的索引
j=j*2+1
} else {
break
}
}
}
