前置知识：完全二叉树

⚡ 30 秒速记

• 完全二叉树：除最后一层都满，最后一层从左往右连续，中间不能空
• 所以能紧凑地塞进数组，不用存指针
• 下标从 0 开始：父 Math.floor((i - 1) / 2)，左孩子 2i + 1，右孩子 2i + 2
• 最后一个非叶结点是 Math.floor(n / 2) - 1，建堆从这里往前下沉
• 它只约束形状，不管大小；加上父子大小关系才是堆

完全二叉树可以理解为「从上到下、从左到右一个挨一个排满」的树，最后一层可以不满，但不能跳着空。 正因为没有空洞，按层序把结点放进数组，下标就能直接算出父子关系，不用存指针。零基下标下，i 的左孩子是 2i + 1，右孩子是 2i + 2，父结点是 Math.floor((i - 1) / 2)。教材上常写的 (n-1)/2 在 JS 里要记得取整，不然会得到小数下标。这个结构只管形状，堆是在它上面再加大小约束。

完全二叉树是指同时满足下面两个条件的二叉树：

• 从第一层到倒数第二层，每一层都是满的，也就是说每一层的结点数都达到了当前层所能达到的最大值
• 最后一层的结点是从左到右连续排列的，不存在跳跃排列的情况（也就是说这一层的所有结点都集中排列在最左边）。

完全二叉树可以是这样的：

也可以是这样的：

但不能是这样的：

更不能是这样的：

注意，完全二叉树中有着这样的索引规律：假如我们从左到右、从上到下依次对完全二叉树中的结点从0开始进行编码：

那么对于索引为 n 的结点来说：

• 索引为 (n-1)/2 的结点是它的父结点
• 索引 2*n+1 的结点是它的左孩子结点
• 索为引 2*n+2 的结点是它的右孩子结点

💬 面试官追问

• JS 里直接写 heap[(i - 1) / 2] 会怎样？

  i = 2 时下标是 0.5，取出来是 undefined。要写 Math.floor((i - 1) / 2) 或 (i - 1) >> 1。

• 如果下标从 1 开始，公式变成什么？

  父 i >> 1，左孩子 2i，右孩子 2i + 1，更简洁。很多教材这么写，就是在下标 0 放个空位。

• 为什么不是完全二叉树就不适合用数组存？

  中间有空位的话数组里也得留洞，最坏一条右斜链要 2^n 的空间。完全二叉树没有洞，n 个结点正好占 n 格。

• 10 个结点的完全二叉树，哪些是叶子？

  最后一个非叶结点是 Math.floor(10 / 2) - 1 = 4，所以下标 5 到 9 都是叶子。建堆只需要从 4 往前处理。

什么是堆

⚡ 30 秒速记

• 堆 = 完全二叉树 + 父子大小约束
• 大顶堆：父 ≥ 孩子；小顶堆：父 ≤ 孩子
• 只保证父子关系，兄弟之间、同层之间没有顺序，数组整体不是有序的
• 读堆顶 O(1)，插入、删堆顶 O(log n)，找任意值还是 O(n)
• 数组存储，缓存友好，JS 没有内置堆，要自己写

堆就是一棵完全二叉树，只多了一条规矩：大顶堆里父结点不小于孩子，小顶堆反过来。 所以堆顶一定是最大或最小值，这是它最大的用处：随时拿极值。但它只管父子，不管兄弟，[9, 8, 6, 3, 1] 是大顶堆，[9, 6, 8, 1, 3] 也是，所以堆不是有序数组，想找某个特定值只能遍历。工程上记住复杂度就够：看堆顶 O(1)，插入和弹出堆顶都是 O(log n)。另外 JS 没有内置的 PriorityQueue，面试一般要手写。