如何证明n个键的堆对应数组A等价于平衡二叉树且深度为Θ(log⁡𝑛)

首先明确讨论前提：我们说的是标准二叉堆的数组存储规则，对于从1开始计数的存储数组A，任意位置i的节点满足：

• 左子节点下标为2*i
• 右子节点下标为2*i+1
• 父节点下标为⌊i/2⌋
  如果数组从0开始计数，仅下标计算规则整体偏移，树的结构完全一致，不影响后续结论。

第一部分：证明对应二叉树的叶子节点深度差至多为1 #

按上述映射规则得到的本质是完全二叉树，推导过程如下：
假设树的最大深度为H（约定根节点深度为1，若约定根深度为0仅数值整体偏移，结论不变）：

1. 前H-1层的节点必然是全满的：如果存在某一层k < H-1有缺失节点，那么缺失节点对应的数组下标会比第H层的节点下标更小，按数组顺序存储的规则，小下标必须先被填充，不可能出现上层留空、下层存节点的情况。前H-1层全满时，总节点数为2^(H-1) - 1。
2. 剩余的n - (2^(H-1)-1)个节点全部位于第H层，且从左到右连续排列，不会出现中间留空的情况。

在这个结构下，所有叶子节点只会出现在两个层：

• 第H-1层：第H-1层中没有子节点的节点，本身就是叶子
• 第H层：所有第H层的节点都是叶子，因为树的最大深度就是H

不存在深度小于H-1的叶子——如果有节点在深度小于H-1的位置且没有子节点，那它的子节点对应的数组下标会比第H层的节点下标小，不可能留空让更大的下标存入第H层的节点。因此所有叶子的深度差最多为H - (H-1) = 1，满足题述的平衡要求。

第二部分：证明树的深度为Θ(log n) #

根据第一部分得到的节点数和深度的关系，可以直接列出不等式：

• 深度为H的树，节点数一定大于前H-1层全满的节点数：n > 2^(H-1) - 1
• 深度为H的树，节点数一定不超过深度为H的满二叉树总节点数：n ≤ 2^H - 1

对不等式做简单变形：

1. 从右侧不等式得：2^H ≥ n + 1 → H ≥ log₂(n+1)
2. 从左侧不等式得：2^(H-1) < n + 1 → H-1 < log₂(n+1) → H < log₂(n+1) + 1

也就是说H的取值始终卡在log₂(n+1)到log₂(n+1)+1的区间内，和log n是同阶量级，满足大Θ记号的定义，因此H = Θ(log n)。

注：堆的堆序性质（父节点键值大于/小于子节点）不影响上述结构结论——只要是按标准数组规则存储的二叉堆，无论节点值如何排列，对应的树结构都满足上述两个性质。

内容的提问来源于stack exchange，提问作者Roeyx