堆排序BUILD-HEAP算法时间复杂度：O(n)还是O(nlogn)？

嘿，你的疑惑太典型了——很多人一开始都会被“n次O(logn)操作”的直觉带偏，但只要拆解节点高度和堆化代价的对应关系，就能明白为什么渐近紧界是O(n)而不是O(nlogn)。

首先先明确BUILD-HEAP的伪代码：

BUILD-HEAP(A)
    heapsize := size(A);
    for i := floor(heapsize/2) downto 1 do
        HEAPIFY(A, i);
    end for
END

核心误区：不是所有HEAPIFY的代价都是O(logn) #

HEAPIFY的时间代价取决于当前节点的高度（这里的高度定义是：节点到叶子节点的最长路径长度，叶子节点高度为0），而不是整个堆的高度。比如：

• 叶子节点（占至少一半的节点）高度为0，HEAPIFY对它们几乎没操作，代价是O(1)；
• 高度为1的节点（占1/4左右）最多只需要下沉1层，代价O(1)；
• 只有靠近根的少数节点，高度接近堆的总高度logn，代价才是O(logn)。

数学推导：加权求和得出线性复杂度 #

假设堆是完全二叉树，总节点数为n，堆的总高度h=⌊log₂n⌋。我们把所有非叶子节点的堆化代价加起来：

总时间T(n) = Σ（从k=1到h）[ 高度为k的节点数量 × O(k) ]

对于完全二叉树：

• 高度为k的节点数量最多为⌈n/(2^{(k+1))⌉，不会超过n/(2}k)；
• 代入求和式后，T(n) = O( n × Σ（k=1到h）k/(2^k) )

这里有个关键的级数求和结论：Σ（k=1到∞）k/(2^k) = 2（可以用幂级数公式推导：Σk*x^k = x/(1-x)²，代入x=1/2得到结果为2）。

因为h是有限的（h=log₂n），所以Σ（k=1到h）k/(2^k) < 2，因此T(n) = O(n×2) = O(n)。

用你举的n=7例子验证 #

当n=7时，堆的总高度h=2：

• 高度为2的节点：1个（根节点i=1），堆化代价O(2)；
• 高度为1的节点：2个（i=2、i=3），堆化代价各O(1)；
• 总代价：O(2+1+1)=O(4)，而n=7，显然是线性关系，远小于O(nlogn)=O(7×3)=O(21)。

总结 #

你之前的错误在于把所有非叶子节点的堆化代价都等价于最大的O(logn)，但实际上大部分节点的堆化代价远低于这个值。通过按节点高度加权求和，就能得出BUILD-HEAP的渐近紧界是O(n)。

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