21 
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)？

4

1 回答 1

19

它需要更仔细的分析，如您将在此处找到的。基本的见解是只有堆的根实际上有深度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)。

于 2018-08-07T21:35:56.220 回答