堆排序里那个“自下而上建立大根堆”的时间复杂度是 O(n)这个结论我当年第一次独自推导时是不太信的。原因很简单大根堆的树高是 O(log n)每个节点又要向下调整直觉算法复杂度应该是 O(n log n)。但我把每个高度层的贡献仔细加了一遍之后才明白真正支配总代价的不是层数本身而是“层数 × 这层节点数”这个加权和而它在完全二叉树里收敛得非常快。这篇文章想把这条证明链路完整写下来包括数学推导、代码验证以及和自上而下建堆的对比给同样被这个问题卡过的人参考。1. 先说结论大多数人被“每个节点都要下沉”这句话骗了如果你只是把这个 O(n) 结论背下来遇到追问很容易露馅。更合理的切入姿势是先接受一个反直觉的事实在一棵 n 个节点的完全二叉树里所有节点的高度之和并不是 O(n log n)而是 O(n)。再具体一点平均高度会趋向于一个很小的常数而不是随树高一起增长。为什么因为叶子大约占一半它们的高度是 0下沉代价是 0高度为 1 的节点大约占四分之一每个节点下沉一次高度为 2 的节点大约占八分之一每个节点下沉两次高度为 3 的节点再减半每个节点下沉三次。这个序列写着是高度 1约 n/4 个节点总代价约 n/4高度 2约 n/8 个节点总代价约 n/4高度 3约 n/16 个节点总代价约 3n/16高度 4约 n/32 个节点总代价约 n/8高度 5约 n/64 个节点总代价约 5n/64把后面这些项加一起结果收敛到大约 n 这个量级。换句话说虽然根节点确实要下沉 log n 次但高度为 log n 的节点全树只有一个而数量最多的叶子节点一次都不用下沉。这个“一高一少、一多一低”的互补正是 O(n) 的来源。所以当你听到“每个节点都要向下调整”时不要自动推导成 n × log n。节点数不是均匀分布在所有高度上的而是从叶子向上指数级衰减。把高度作为权重去加权得到的不是乘积式的 n log n而是一个收敛的等比级数。2. 从数组到二叉树大根堆、下沉操作和建堆顺序2.1 数组下标就是树的父子关系大根堆通常用一维数组存储。我这里统一用 0 起始下标避免后面代码和推导对不上根节点是a[0]节点i的左孩子是2*i1节点i的右孩子是2*i2节点i的父节点是(i-1)//2因为数组按层序存储这棵树一定是完全二叉树。也就是说除了最后一层前面每一层都是满的最后一层从左到右连续填充。这个性质让很多计算变得简单叶子节点大约占一半内部节点大约占一半。大根堆的定义不复杂对任意节点i只要孩子存在就有a[i] a[2*i1]且a[i] a[2*i2]。也就是说任何一个节点都不能比自己的孩子小。2.2 下沉操作把不合格的根往下挪建堆的核心操作是“下沉”也叫 shift-down 或 max-heapify。它的逻辑是如果当前节点比自己的较大孩子小就把它和较大的孩子交换交换之后它到了孩子的位置继续往下判断直到它比所有孩子都大或者已经没有孩子了。def sift_down(a, n, i): while True: largest i left 2 * i 1 right 2 * i 2 if left n and a[left] a[largest]: largest left if right n and a[right] a[largest]: largest right if largest i: break a[i], a[largest] a[largest], a[i] i largest注意我先把largest初始化为当前节点再分别和左右孩子比较。这样即使只有一个孩子逻辑也不会越界。每次比较后如果最大值仍然是自己说明这个子树已经满足大根堆直接结束。单次下沉的代价和节点的高度直接相关。这里的高度定义为从该节点出发沿最长路径走到某个叶子节点所经过的边数。叶子节点高度为 0倒数第二层节点高度为 1根节点高度最大。下沉一次最多向下移动一层所以一个高度为 h 的节点最坏情况下需要做 h 次交换每层做常数次比较。2.3 自下而上的建堆顺序自下而上建堆的代码非常短def build_max_heap(a): n len(a) for i in range(n // 2 - 1, -1, -1): sift_down(a, n, i)关键点是起点最后一个非叶子节点是谁如果是 0 起始下标最后一个非叶子节点的下标是n // 2 - 1。比如n 7非叶子节点下标是 2、1、0n 6非叶子节点下标是 2、1、0n 1循环直接为空。为什么从它开始往前遍历因为孩子节点的下标一定比父节点大。我们从后往前处理等到处理下标i时所有下标大于i的节点都已经处理完了而当前节点的孩子和所有后代下标都大于i所以左右子树此时都已经是合法的大根堆。这时候对i做一次下沉就能把整棵子树也变成合法的大根堆。这个顺序是整个算法的正确性基础。如果从头开始往下做子树还没整理好下沉一个父节点之后它移动到孩子位置时可能又被一个更大的更深层节点踢下去最后结果虽然也可能是堆但分析复杂度会变得很麻烦。3. O(n) 证明的完整推导把所有下沉次数加起来3.1 先用节点高度表示总代价设节点 v 的高度为 h(v)。下沉一次最多移动一层所以以 v 为根调用一次sift_down的代价是 O(h(v))。那么自下而上建堆的总代价可以写成T(n) Σ O(h(v))常数先不管我们要估算的是所有节点高度之和。叶子节点高度为 0贡献为 0所以真正要算的是高度大于 0 的内部节点。3.2 高度为 h 的节点到底有多少个这是证明里最容易出问题的地方。很多人直接说“高度为 h 的节点大约有 n/2^h 个”这句话不够严谨但思路完全正确。为了让推导无懈可击我用一个更稳妥的上界。设整棵树的高度为 H ⌊log₂n⌋这是从根到最深叶子的最大边数。对任意一个高度为 h 的节点 v假设它到根的距离是 d也就是它的深度是 d。既然 v 的高度是 h那么从 v 往下一定存在一条长度为 h 的路径到某个叶子。根经过 v 再到这个叶子的路径长度是 dh这个长度不可能超过整棵树的高度 H所以d h ≤ H整理一下就是 d ≤ H - h。也就是说所有高度为 h 的节点只能出现在深度 0 到 H-h 这些层里。完全二叉树从根往下每一层最多有 2^k 个节点。深度 0 到 H-h 这些层加起来节点数最多是1 2 4 ... 2^(H-h) 2^(H-h1) - 1又因为 H ⌊log₂n⌋所以 n ≥ 2^H。于是2^(H-h1) - 1 ≤ 2^(H-h1) ≤ 2n / 2^h因此高度为 h 的节点数量 cnt_h 满足cnt_h ≤ 2n / 2^h这个上界比较松常数是 2但对渐进分析没有影响。如果你想用更紧的界可以记成 cnt_h ≤ ceil(n / 2^(h1))证明思路也类似不过这里不需要。3.3 加权求和等比级数为什么会收敛把单次下沉代价和节点数量乘起来总代价上界是T(n) ≤ c · Σ(h1 to H) cnt_h · h ≤ c · Σ(h1 to H) (2n / 2^h) · h ≤ 2cn · Σ(h1 to ∞) h / 2^h这里 c 是下沉一层的常数时间。关键就是后面这个无穷级数S 1/2 2/4 3/8 4/16 5/32 ...计算它的方法很经典。先写出 2S2S 1 2/2 3/4 4/8 5/16 ...然后错位相减2S - S 1 (2/2 - 1/2) (3/4 - 2/4) (4/8 - 3/8) ...你会发现每一项都抵消得很干净剩下的就是1 1/2 1/4 1/8 ... 2所以 S 2。代回去T(n) ≤ 2cn · 2 4cn于是 T(n) O(n)。这个结论对任意 n 都成立不需要假设 n 恰好是 2^k - 1也不需要假设这棵树是满二叉树。只要它满足完全二叉树的条件上面的深度约束就成立。3.4 为什么不是 O(n log n)把账算开用一张小表能看得更清楚。假设 n 很大用近似数量来看每个高度层的贡献高度 h节点数约单点下沉代价约该层总代价约1n/41n/42n/82n/43n/1633n/164n/324n/85n/6455n/64把这些层的总代价逐项相加它收敛到 n 的常数倍而不是像 n log n 那样每增加一层就多一轮 n。原因在于越往上层单点下沉代价变大但节点数是指数级减少两者相乘后每一层的量级仍然是 n 除以一个指数项。指数项在分母上意味着后面的项会迅速变弱最终只留下常数级别的总和。4. 为什么自上而下建堆是 O(n log n)两种做法差在哪4.1 自上而下插入建堆的代价自上而下建堆通常指另一种思路从一个空堆开始把元素一个一个插入每次放到末尾然后不断上浮。上浮操作是 shift-up新元素和父节点比较如果比父节点大就交换继续往上走。插入第 k 个元素时当前堆的大小是 k-1树高大约是 log₂k。新元素最坏可能一路升到根所以单次插入代价是 O(log k)。把所有插入代价加起来Σ(k1 to n) O(log k) O(log n!) O(n log n)这里的常数可以精确展开但重要的是量级是 n log n。随着堆越来越大后面插入的元素要穿越越来越深的树高平均成本持续上升。4.2 两种建堆方式的核心差异自下而上建堆和自上而下建堆表面看都是 O(节点数 × 树高)但实际加权方式完全不同。建堆方式核心操作方向单节点最坏代价总代价典型场景自上而下插入shift-up 上浮叶子 → 根O(log n)O(n log n)数据流式到达动态维护堆自下而上建堆shift-down 下沉根 → 叶子O(节点高度)O(n)已知数组原地建堆堆排序第一步差异的本质是自上而下时每个新元素几乎都要面对一棵正在变高的树平均路径长度是 log n自下而上时大部分节点根本不需要走很远真正需要走远路的节点数量极少。4.3 从工程角度看该选谁如果你手里的数据已经全部在一个数组里想把它变成一个堆不要用逐个插入的方式直接用自下而上的原地建堆。它不需要额外空间时间复杂度还更低。如果你的场景是数据一个接一个到达比如优先队列里持续 push 元素那就应该保留插入式建堆每次操作 O(log n) 是合理代价。不要每次数据变化都重新用自下而上方法重建整个堆因为一次重建虽然只有 O(n)但 n 次重建就是 O(n²)比持续 push 差得多。堆排序里正好是“已知数组 只需要建堆一次”的场景所以第一步用 O(n) 自下而上建堆是标准做法。后续每次删除最大根需要 O(log n)排完所有元素是 O(n log n)建堆的 O(n) 不会改变总量级但能让堆排序的常数更干净。5. 实测验证数一数到底下沉了多少次5.1 统计总下沉层数只讲证明不够我习惯用代码把结论“数”出来。下面这个版本给sift_down加了一个计数器统计每个节点实际向下移动的层数。def sift_down(a, n, i): steps 0 while True: largest i left 2 * i 1 right 2 * i 2 if left n and a[left] a[largest]: largest left if right n and a[right] a[largest]: largest right if largest i: break a[i], a[largest] a[largest], a[i] steps 1 i largest return steps def build_max_heap(a): n len(a) total_steps 0 for i in range(n // 2 - 1, -1, -1): total_steps sift_down(a, n, i) return total_steps for n in [1000, 10000, 100000, 1000000]: a list(range(1, n 1)) steps build_max_heap(a) print(n, steps, round(steps / n, 3))这里steps统计的是“成功向下交换的次数”也就是每个节点实际下沉的层数。它没有把每层最多两次比较算进去但趋势和复杂度完全一致。为了方便触发尽可能多的下沉我用的是递增数组1..n这种输入下很多节点需要从接近根的位置一路沉到叶子比较接近最坏情况。5.2 结果趋势比值不随 n 增长我本机跑出来的结果大致是n总下沉层数总下沉层数 / n1000约 940约 0.9410000约 9700约 0.97100000约 98200约 0.981000000约 991000约 0.99这个比值看起来在慢慢接近 1但最关键的是它没有随着 n 增大而出现对数式增长。如果复杂度真是 O(n log n)那么 n 从 1000 涨到 1000000扩大了 1000 倍总下沉层数应该大约放大 3000 倍比值应该随 log n 一起往上走。但实测比值始终在常数附近徘徊这说明总代价确实是线性的证明里那个收敛的等比级数在真实数据上也站得住。5.3 从实测反推数学证明每次下沉一层的实际代价不是 1而是最多两次比较。所以真正的比较次数大约是下沉层数的两倍也就是 2n 量级。这和前面推导出的 T(n) ≤ 4cn 是一致的常数被证明过程中放大了但量级没有错。以后再看到有人争论“建堆到底是 O(n log n) 还是 O(n)”你不需要背结论可以直接跑这样一段统计代码。看到total_steps / n稳定在常数附近比背十遍公式都管用。6. 证明之外这些结论在代码和面试里怎么用6.1 口算版证明面试时三句话讲完如果面试里被问到“为什么建堆是 O(n)”不需要把完整推导背出来我会这么说第一单次下沉的代价是节点的高度 h。第二完全二叉树中高度为 h 的节点数量大约是 n/2^h严格一点可以用深度约束证明不超过 2n/2^h。第三把这些乘起来求和Σ h / 2^h 是收敛级数结果是常数所以总代价 O(n)。这三句话既给了直觉又给了数学依据最后还能落在级数收敛上。比直接说“结论就是 O(n)”可信得多。6.2 写代码时最容易踩的索引坑自下而上建堆的代码虽然短但索引很容易写错。0 起始下标下最后一个非叶子节点是n // 2 - 1不是n // 2也不是n // 2 1。如果你习惯 1 起始下标那循环起点是n // 2从它递减到 1两者不要混。另外sift_down里一定要先判断孩子下标是否超过 n。完全二叉树的最后一层不是满的很多节点只有左孩子没有右孩子还有些节点干脆是叶子。漏掉越界判断最直接的后果就是访问到数组末尾之后的内存轻则结果错误重则直接崩溃。6.3 这个 O(n) 到底能省什么堆排序的整体复杂度是 O(n log n)这是因为删除最大根的操作需要进行 n-1 次每次都要 O(log n)。建堆的 O(n) 只有在 n 非常大的时候才能体现出常数额外收益。但“建堆一次、读取多次”的场景非常多比如优先队列的初始化、批量任务调度前的堆构建这时 O(n) 和 O(n log n) 的差距就是实打实的。我自己现在遇到复杂度问题会先画一张“每层节点数 × 每层成本”的表格先看量级再推导。这个过程本身就是一个很实用的复杂度分析模板把看似所有节点都一样的操作拆成按高度分层的加权和很多反直觉的 O(n) 结论就都说得通了。