为什么“heapq.heapify”的实现工作有效？

Question

我试图理解如何将列表转换为最小堆。我自己做了一个简单的递归实现，看起来很有效，但我很想了解heapq.heapify是如何工作的。将数组表示为堆，策略是确保在所有非叶索引处都满足堆不变量。这证明实施的第一部分是合理的：

def heapify(x):
    for i in reversed(range(n//2)):
        _siftup(x, i)

因此，我们期望_siftup(x, i)应该确保在索引i处满足堆不变量

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        # Move the smaller child up.
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and bubble it up
    # to its final resting place (by sifting its parents down).
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)

def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

这似乎首先向上移动我们开始使用的任何节点的最小子节点，直到该节点的值为叶（_siftup）。然后它向下移动该叶的父级，以找到该叶的值在堆中的正确位置（_siftdown）。为什么这比下面简单的递归实现更“有效”？库提到了这种情况，但没有解释原因

def build_min_heap(arr: List[int]):

    n = len(arr)

    for i in reversed(range(n//2)):
        _make_heap_invariant(arr, i)

def _make_heap_invariant(arr: List[int], i: int):

    n = len(arr)
    l_child_idx = 2*i + 1 if 2*i + 1 < n else None
    r_child_idx = 2*i + 2 if 2*i + 2 < n else None
    if l_child_idx and arr[i] >= arr[l_child_idx]:
        arr[i], arr[l_child_idx] = arr[l_child_idx], arr[i]
        _make_heap_invariant(arr, l_child_idx)
    if r_child_idx and arr[i] >= arr[r_child_idx]:
        arr[i], arr[r_child_idx] = arr[r_child_idx], arr[i]
        _make_heap_invariant(arr, r_child_idx)

Answer 1

大多数计算机科学教科书都应该有一篇关于堆的文章。基本不变量是对于堆中的任何索引i

• heap[i] ≤ heap[2 * i + 1]如果2 * i + 1是合法索引，并且
• heap[i] ≤ heap[2 * i + 2]如果2 * i + 2是一个合法的索引

这两个条件保证heap[0]是堆中最小的元素

从堆中删除最小的元素和向堆中添加元素都可以在O（logn）时间内完成