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)), Внизу, на узле, расположенном над листом, где живет половина узлов, лист попадает на первую итерацию внутреннего цикла.