小编Rah*_*ger的帖子

我试图重新实现 heapify 方法，以便使用_siftup和_siftdown更新或删除堆中的任何节点并保持 O(log(n)) 的时间复杂度。

我做了一些努力来优化我的代码，但事实证明它们比heapq.heapify （就花费的总时间而言）更糟糕。所以我决定研究源代码。并将复制的代码与模块的代码进行比较。

# heap invariant.
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

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos …