为何Python的heap_maker方法时间复杂度是O(N)而非O(N log N)？

我无法理解为何以下Python中的heap_maker方法时间复杂度为O(N)，我原本认为它应该是O(N log N)，因为存在嵌套循环，最坏情况下每个元素可能需要向下堆化并与其他元素进行比较，难道不是这样吗？

def heap_maker(self, ca: ComplexArray) -> None:
    """
    Takes a complex array object in as an argument and builds
    a heap object based upon the values in the complex array
    """
    self._heap = ca #complex array can be considered like a normal python list

    #build the heap using heapify down
    n = self._heap.length() #length is O(N)
    for i in range(n // 2, -1, -1):
        j = i
        while 2 * j + 1 < n:
            left = 2 * j + 1
            right = 2 * j + 2 if 2 * j + 2 < n else left
            k = left if self._heap[left] < self._heap[right] else right
            if self._heap[j] > self._heap[k]:
                self._heap[j], self._heap[k] = self._heap[k], self._heap[j]
            else:
                break
            j = k

解答 #

你之所以会误以为是O(N log N)，是默认了每个节点都要执行O(log N)次堆化操作，但实际上不同层级的节点需要堆化的次数是不一样的：

• 堆的最后一层是叶子节点，不需要执行任何堆化操作（代码里从n//2开始循环，直接跳过了这些节点）。
• 倒数第二层的节点，最多只需要向下堆化1次就能调整到位。
• 倒数第三层的节点，最多需要堆化2次。
• 以此类推，堆顶节点（第0层）最多需要堆化log2(N)次。

我们可以通过求和来计算总操作数：
假设堆的高度为h（h ≈ log2(N)），第k层（从0开始计数）的节点数量是2^k，每个节点最多需要h - k次堆化操作。总操作数就是：
$$\sum_{k=0}^{h-1} 2^k \times (h - k)$$

这个求和的结果最终会收敛到2N - 2，也就是**O(N)**的时间复杂度。

简单来说，大部分节点（底层节点）只需要很少的堆化操作，少数顶层节点需要较多操作，但整体加权下来总操作数是线性的，而非线性对数级。

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