Python heapify() 时间复杂度

Question

def heapify(A):
    for root in xrange(len(A)//2-1, -1, -1):
        rootVal = A[root]
        child = 2*root+1
        while child < len(A):
            if child+1 < len(A) and A[child] > A[child+1]:
                child += 1
            if rootVal <= A[child]:
                break
            A[child], A[(child-1)//2] = A[(child-1)//2], A[child]
            child = child *2 + 1

这是 python heapq.heapify() 的类似实现。文档中说这个函数的运行时间为 O(n)。但看起来对于 n/2 个元素，它执行 log(n) 操作。为什么是O(n)？

Answer 1

它需要更仔细的分析，例如您将在这里找到。基本的见解是，只有堆的根实际上具有深度

log2(len(a))

。在叶子上方的节点处（一半节点所在的位置），在第一次内循环迭代时会击中叶子。

“精确”推导

挥挥手，当算法正在寻找具有

N

元素的子树根节点时，每个子树中大约有

N/2

元素，然后需要与

log(N)

成比例的工作来合并根并将这些子堆合并为单个堆。所以总共需要的时间

T(N)

大约是

T(N) = 2*T(N/2) + O(log(N))

这是一种不常见的复发情况。不过，可以使用 Akra–Bazzi 方法 来推断它是

O(N)

。

我认为从头开始得出精确的解决方案更能提供信息，当然也更令人满意。为此，我只会讨论完整的二叉树：在每个级别上都尽可能完整。那么总共有

2**N - 1

个元素，所有子树也都是完全二叉树。这回避了关于当事情不完全平衡时如何进行的大量毫无意义的细节。

当我们查看具有

2**k - 1

元素的子树时，它的两个子树各恰好有

2**(k-1) - 1

个元素，并且有

k

个级别。例如，对于具有 7 个元素的树，根部有 1 个元素，第二层有 2 个元素，第三层有 4 个元素。子树堆化后，根必须移动到位，将其向下移动 0、1 或 2 层。这需要在级别 0 和 1 之间进行比较，也可能需要在级别 1 和 2 之间进行比较（如果根需要向下移动），但仅此而已：所需的工作与

k-1

成正比。总而言之，

T(2**k - 1) = 2 * T(2**(k-1) - 1) + (k - 1)*C

对于一些常数

C

限制比较一对相邻级别的元素的最坏情况。

T(1)

呢？那是免费的！只有 1 个元素的树已经是一个堆 - 没有什么可做的。

T(1) = 0

在这些叶子之上一层，树有 3 个元素。将最小的（对于最小堆；最大的对于最大堆）移动到顶部的成本（不超过）

C

。

T(3) = C

树上一层有 7 个元素。堆积每个子树的成本为

T(3)

，然后将根移动到位的成本不超过

2*C

：

T(7) = 2*C + 2*C = 4*C

以同样的方式继续：

T(15) = 2* 4*C + 3*C = 11*C
T(31) = 2*11*C + 4*C = 26*C
T(63) = 2*26*C + 5*C = 57*C
...
T(2**k - 1) = (2**k - k - 1)*C

最后一行是对一般形式的猜测。您可以验证它之前的所有特定行是否“有效”，然后通过归纳法来证明它很简单。

所以，

N = 2**k - 1

，

T(N) = (N - log2(N+1)) * C

这表明

T(N)

的边界是

C*N

，所以

O(N)

也是如此。

Answer 2

对于更多数学爱好者： 考虑一个具有 L 个级别的完全二叉树，标记为从 0（根）到 L-1。这样的树有 N=2^L-1 个节点。相反，具有 N 个节点的完全二叉树具有 L=log2(N-1) 个级别。

对于任何给定的 l 级节点，bubble/heapify down 操作会进行 L-1-l 比较。对于操作总数，我们需要计算总和：

等于

注意：严格来说，总和是从 0 到 L-2，因为叶子不进行操作。然而，L-(L-1)-1 为零，因此我们可以将总和上限保留为 L-1