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))。在第一个内循环迭代中，在一片叶子上方的节点（其中一半的节点居住）下方向下击中一片叶子。