堆排序里有个很反直觉的结论把无序数组建成大根堆自下而上一层层调整总时间竟然只有 O(n)。我第一次看到这个结论时完全不信——明明循环里套循环怎么可能不是 O(n log n)后来被面试官连续追问了几次才老老实实坐下来把证明推清楚。这篇文章就是那次“补课”的完整记录内容包括建堆两种路线的本质差别、自下而上建堆的实现细节、两个不同角度的严格数学证明以及实际写堆排时候踩过的坑。适合正在学数据结构、准备算法面试或者想真正搞懂教材里那句“建堆 O(n) 到底怎么来的”的读者。1. 建堆这件事远没有看起来那么简单1.1 先搞清楚我们在堆什么堆排序里的大根堆本质上是一棵完全二叉树加上一条约束任意父节点的值不小于它的子节点。因为数组天然可以映射成完全二叉树——下标 i 的左右孩子是 2i1 和 2i2从 0 开始计数——所以“建堆”就是把一段无序数组调整成满足这条约束的形态。堆排序的整体套路是先建堆再反复把堆顶最大值挪到数组末尾同时缩小堆的范围并对新堆顶做“下滤”。很多人背代码时一气呵成但真正值得抠细节的恰恰是第一步建堆。1.2 两条建堆路线结论天差地别建堆有两条路线。第一条是自顶向下逐个插入从空堆开始每次往末尾追加一个元素然后执行“上滤”让这个新元素一路向上找到自己该待的位置。因为每次插入最多上滤 O(log n) 层所以 n 个元素的总代价是 O(n log n)。第二条是自下而上就地调整从最后一个非叶节点开始对每个节点执行“下滤”——把这个节点沿着值更大的孩子一路下沉直到满足大根堆约束。这条路线就是本文的主角结论是 O(n)。两条路线做的事情完全一样最终都能得到一个合法的大根堆但复杂度差了一个 log n 因子。这个差异的根源一句话就能说清自顶向下插入时越晚插入的元素越可能从堆底一路爬到堆顶平均路径长而自下而上调整时绝大多数节点本来就待在树的中下层它们下沉的步数极短少数靠近根的节点虽然单次下沉步数多但数量少得可怜。这就像搬砖上楼自顶向下是每次从一楼搬到顶楼自下而上则是先让高楼层的人往下搬几步让低楼层的人摊上大部分体力——总步数完全不同。1.3 为什么非要较真这个 O(n)有人会说堆排序整体复杂度反正都是 O(n log n)建堆是 O(n) 还是 O(n log n) 有什么影响这个想法大错特错。一方面堆排序的常数差距在数据量大的时候非常明显。建堆阶段 O(n) vs O(n log n)在 100 万条数据上就差大概 20 倍的建堆耗时。另一方面建堆这个操作本身不只是服务于堆排序优先级队列初始化、Dijkstra 算法里的最小值堆、TopK 问题里用于维护候选集合的小顶堆全都依赖“把一个数组快速整理成堆”的能力。在这些场景里O(n) 和 O(n log n) 的差距直接决定了整个算法的规模上限。再者面试官问“堆排序建堆复杂度是多少”其实考察的就是你能否解释清楚这个反直觉的结论。如果只答“O(n)”却讲不出为什么对方大概率会追问到你露馅。所以这篇文章的核心就是把证明过程掰开揉碎。2. 自下而上建堆的关键细节2.1 从哪个节点开始下手自下而上建堆的起点不是最后一个元素而是最后一个非叶节点。数组长度为 n下标从 0 开始最后一个非叶节点的下标是 n // 2 - 1。这个结论可以自己推一遍设某个节点下标为 i如果它有左孩子那么左孩子下标是 2i1。最后一个有孩子的节点就是满足 2i1 n 的最大 i所以 i (n-1)/2整数下取整就是 i n//2 - 1。为什么从这个节点开始而不是从 n-1 开始因为叶子节点没有孩子天然满足大根堆约束不需要调整。从最后一个非叶节点往前遍历每一步调用一次 heapify 下滤操作就能保证“当处理到某个节点时它左右两个子树都已经是合法的大根堆”。这个不变量是自下而上建堆正确的关键面试时如果能把这句话说出来比背十行代码都有用。2.2 下滤过程的关键判断下滤heapify / sift-down的代码看起来短但有几个细节容易被忽略。首先比较的时候不能只看左孩子。标准的 heapify 是先把当前节点记为 largest然后分别比较左孩子和右孩子谁大谁当 largest。如果 largest 不是当前节点就交换两者的值然后递归进入被交换的那个孩子子树继续下滤。这里最容易写错的地方是只比较了两个孩子、直接把大的那个孩子的值换上来却没有更新 largest 的指向。比如当前节点是 5左孩子是 9右孩子是 8只比较左孩子就把 5 和 9 换了结果右孩子 8 比父节点 5 还大堆性质被破坏。正确做法是先把 8 和 9 比出最大值再决定换不换。其次下滤是沿着“较大孩子”所在的路径下沉。为什么要沿着较大孩子因为大根堆要求父节点不小于所有孩子——只要父节点不小于最大的孩子就自然不小于另一个孩子。如果沿着较小孩子下沉就算换上来后满足了父节点和较小孩子的关系却可能仍然违反和较大孩子的关系白做一次交换。最后递归终止的条件是当前节点已经是叶子或者它已经比两个子节点都大。叶子节点的判断很简单左孩子下标 2i1 n。2.3 按层统计工作量直觉先行正式证明之前先建立一个直觉。完全二叉树里靠近底层的节点数量非常多但它们下沉步数极少靠近根部的节点数量很少但每个节点最多下沉 h 步h 是树高。假设树高是 h可以粗略地把总工作量拆成第 h-1 层的节点倒数第二层最多有大约 n/4 个每个下沉最多 1 步第 h-2 层的节点最多 n/8 个每个下沉最多 2 步第 h-3 层的节点最多 n/16 个每个下沉最多 3 步……换句话说总工作量近似为n/4 · 1 n/8 · 2 n/16 · 3 …这个级数每一项的数量级都在快速衰减。直觉上n/8 个节点每人走 2 步贡献是 n/4n/16 个节点每人走 3 步贡献是 3n/16已经比上一项小。把这些项加起来总量是 n 的常数倍而不是 n log n。为什么自顶向下插入建堆做不到这样因为插入建堆时每一次新元素上滤都是从底部出发而底部恰恰是节点最多的地方。每插入一个元素最坏情况都要一路爬到根成本是 log n插入 n 个元素总成本就是 n log n。同样是建堆一个让成本集中在少数节点上一个让每个节点都承担差不多的成本差距就这么来的。3. 严格证明为什么是 O(n)3.1 代码先行证明有了载体先把自下而上建堆的完整实现亮出来后面每一步证明都能对着代码看。def heapify(arr, n, i): 对以 i 为根的子树执行下滤使其满足大根堆性质 largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) def build_max_heap(arr): n len(arr) # 从最后一个非叶节点开始自下而上逐个下滤 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i)复杂度分析的难点在于heapify 内部的 while/递归并不是每次都会跑到叶子不同节点下沉的步数差异极大。所以不能简单地写“有 n 个节点每个最多下沉 log n 层所以是 O(n log n)”——这种粗糙分析就是很多人误判的根源。3.2 方法一精确级数求和设完全二叉树高度为 h ⌊log₂ n⌋根节点在第 0 层。第 k 层的节点数最多为 2^k第 k 层节点往下沉时最多还需要下沉 h-k 次因为该节点所在的子树最多还有 h-k 层。因此总下滤次数 T(n) 的上界是T(n) ≤ Σ_{k0}^{h} 2^k · (h-k)这个式子每一项的意思就是第 k 层最多有几个节点乘上每个节点最多下沉几步。接下来做换元。令 j h - k那么当 k 从 0 变到 h 时j 从 h 变到 02^k 2^(h-j)h-k j。于是T(n) ≤ Σ_{j0}^{h} j · 2^(h-j) 2^h · Σ_{j0}^{h} j / 2^j关键一步来了。对于任意有限的 h有Σ_{j0}^{h} j / 2^j ≤ Σ_{j0}^{∞} j / 2^j而后者是一个经典的级数求和结果等于 2。这个结果可以用幂级数公式推出对任意 |x| 1有Σ_{j0}^{∞} j·x^j x · d/dx (Σ_{j0}^{∞} x^j) x · d/dx (1/(1-x)) x / (1-x)^2代入 x 1/2得到 2。所以T(n) ≤ 2^h · 2 2^(h1)现在还需要把 2^(h1) 变成 n 的同阶量。因为 h ⌊log₂ n⌋所以 h1 ≤ log₂ n 1于是2^(h1) ≤ 2·2^(log₂ n) 2n最终得到T(n) ≤ 2n也就是说自下而上建堆的下滤总次数被 2n 这个常数严格压住复杂度自然就是 O(n)。这个方法有一个优点它不依赖任何“平均情况”的假设直接对最坏情形做级数估计。哪怕数组故意设计成让每个节点都走向最坏路径总步数也超不过 2n。换句话说O(n) 是自下而上建堆的最坏时间复杂度不是平均情况。3.3 方法二按离叶子层的距离加权级数求和固然严谨但对很多人来说还是有点绕。再给一个更贴近直觉的证明视角按“节点离叶子层的距离”来分组统计。定义距离 d 为某个节点到其子树叶子节点的最大层数。叶子节点 d 0无需下滤。对于 d ≥ 1 的节点考虑它所在的层。高度为 h 的完全二叉树中离叶子距离为 d 的节点一定在第 h-d 层这层节点数最多是 2^(h-d)。而 n ≥ 2^h高度为 h 的完全二叉树至少包含 2^h 个节点所以2^(h-d) ≤ n / 2^d于是离叶子距离为 d 的节点每个最多下滤 d 步总工作量上界是(d · n) / 2^d对 d 从 1 到 h 求和T(n) ≤ Σ_{d1}^{h} d · n / 2^d n · Σ_{d1}^{∞} d / 2^d n · 2 2n这个证明本质上和第一种方法一致但换了一个更直观的分组方式不按“从上到下的层”分组而是按“到叶子有多远”分组。绝大多数节点离叶子很近所以承担的权重极小。这里面有一个很妙的直觉完全二叉树里一半以上的节点都是叶子直接跳过剩下的一半里又有大部分只需要下沉 1 步或 2 步。真正需要下沉很多步的节点数量以指数速度递减所以总工作量被压得很低。为了加深理解可以算一笔具体账。如果 n 2^10 - 1 ≈ 1023满二叉树那么叶子层 512 个节点工作量 0倒数第二层 256 个节点每个下沉 1 步共 256倒数第三层 128 个节点每个最多下沉 2 步共 256倒数第四层 64 个节点每个最多下沉 3 步共 192……把这些加起来总步数不会超过 1023 的 2 倍。而如果所有节点都按 log n 步算那将是 1023×10 ≈ 10230 步。两者差了近一个数量级。这就是 O(n) 和 O(n log n) 的实际差距。3.4 对比自顶向下插入差在哪里把两种建堆方式并排放在一起复杂度的分野会更清晰。自顶向下插入建堆的代价是T(n) Σ_{i1}^{n} O(log i) O(n log n)为什么自顶向下插入避不开这个 log n因为每插入一个新元素它从一开始就处在堆的底部区域。底部是节点最多、最容易聚集大量“待处理”元素的地方而上滤路径的长度等于该节点当前的高度平均来说与 log n 同阶。也就是说几乎每个插入操作都支付了大约 log n 的代价。而自下而上建堆则完全不同建堆的过程等价于让每个节点的“上滤/下滤成本”和“该节点到叶子区域的距离”挂钩。叶子区域节点多但距离近根部区域距离远但节点少。于是总成本表现为收敛级数而非调和级数这就是 O(n) 与 O(n log n) 的分水岭。如果读者对公式不敏感可以想象一个健身房发哑铃的场景自顶向下插入是给每个新会员都发一对最重的哑铃所有人都要堆到顶楼自下而上建堆则是先数清楚每层楼的人数楼层越低发越轻的哑铃让大多数人只在低楼层活动。整体的人力消耗完全不一样。4. 实操避坑与自测技巧4.1 最容易错的三个认知坑一把“自下而上建堆”和“自顶向下插入”搞混。很多人写 build_max_heap 时for 循环方向写反从 0 到 n 逐个调用 heapify。这样其实等价于自顶向下插入复杂度变成 O(n log n)。判断方法很简单看 heapify 的方向。自下而上建堆一定是从 n//2-1 递减到 0对每个下标调用一次下滤如果从 0 递增到 n-1那是边插入边上滤的变形不是教科书里的线性建堆。坑二认为“堆排序每次删除堆顶都要下滤 log n 次所以堆排序里建堆也应该是 O(n log n)”。这里混淆了两个不同阶段。删除堆顶时堆的范围在不断缩小每次对新的堆顶执行下滤最坏要走 log(当前堆大小) 步这个阶段确实是 O(n log n)。但建堆阶段的下滤对象是树中各个层级的节点成本分散所以是 O(n)。两个阶段的特性完全不同不能用一个粗略的“每个节点都走 log n”概括。坑三把证明里的常数误解成平均情况。本文前面推导的上界 2n 是最坏情况上界不依赖随机分布。哪怕用一个反着排的数组也就是最不可能直接满足堆性质的输入自下而上建堆的总步数也仍然被 2n 压住。4.2 用代码验证你的建堆复杂度想验证自己的实现是不是真的 O(n)最直接的方法是数比较次数。在 heapify 里加计数器跑一组随机数据观察总比较次数和 n 的关系import random count 0 def heapify(arr, n, i): global count largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right count 1 # 每组 if 判定的开销视作一次代价 if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) def build(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for size in [1000, 2000, 4000, 8000, 16000, 32000, 64000]: data [random.randint(0, 10**9) for _ in range(size)] count 0 build(data) print(size, count)实测下来size 从 1000 翻倍到 64000 时count 基本也是线性增长翻倍输入 count 略翻倍而不是翻倍后多一个固定倍数。如果把自顶向下插入的逻辑写成同样风格去计数count 会呈现出 n log n 的增长趋势。这个实验特别适合拿来向别人证明“这个 O(n) 不是玄学”。4.3 面试被追问时怎么答面试里如果被问到“为什么自下而上建堆是 O(n)”一个清晰的回答套路是第一句指出关键不是所有节点都承担同样的成本。第二句给出级数第 k 层最多 2^k 个节点每个节点最多下沉 h-k 次所以总操作是 Σ 2^k(h-k)。第三句说明这个级数收敛换元后变成 2^h·Σ(j/2^j)而 Σ j/2^j 是收敛的等比型级数等于 2所以总量是 O(2^h)也就是 O(n)。这个回答比丢出一句“教材上就是这么写的”有说服力得多。如果面试官进一步问常数是多少还能补一句最坏上界不超过 2n 次下滤不算递归调用本身的开销。大部分面试官听到这个程度就会满意了。另外如果要在白板上手写建议先写清楚 heapify 再写 build同时在 build 的循环处注释一句“从最后一个非叶节点开始确保左右子树已满足堆性质”。这个注释既是提醒自己也是向面试官展示你理解每一步的前提条件。我个人在实际写堆排时的体会是与其死记结论不如把级数求和亲自推两遍。第一次推会觉得就是代数变形第二遍推会发现真正核心的洞察是“节点数量随层数指数增长而单节点下沉步数随层数线性增长两者相乘后再求和是收敛的”。有了这层理解以后看到任何基于完全二叉树的分治算法都会下意识先按层估算工作量而不是笼统地说“每层 n 个、每层 log n”。这个思维习惯比背下一个 O(n) 结论值钱得多。