1

我正在阅读heapq的源代码，发现_siftup func最后调用了_siftdown。我认为这有点多余。我想知道这真的有必要吗？

我对这两种情况进行了测试，但我没有发现这两种情况之间有任何区别。测试代码如下（heap_test 是 heap 的副本，并注释了 _sifup 的最后一行）：

from heapq_test import heapify as heapify_test

import heapq
import random

for _ in range(200000):
    a = [random.randint(0, 30) for _ in range(100)]
    b = a.copy()
    heapify_test(a)
    heapq.heapify(b)
    assert a == b
4

2 回答 2

2

_siftup 函数的最后一个 _siftdown 是必要的。一个例子有帮助。

堆 = [1,1,1,3,4,5,1]

如果你删除 _siftup 中的最后一个 _siftdown 并执行 heappop() 你会得到 [1, 1, 5, 3, 4, 1] 这不是一个堆。

最后一个 _siftdown 是必要的，因为下面代码中的 while 循环（来自 heapq 源代码）只选择较小的孩子，但没有将新项目的值与 child 进行比较，所以最后我们需要一个 _siftdown。而作者为什么要这样实现_siftup函数呢？为什么它会继续寻找较小的孩子，直到_siftup 中的一片叶子被击中？您可以在源代码中 _siftup 函数上方的作者评论中获得这些信息。

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)

希望这个回复对你有帮助。

于 2020-07-11T08:04:15.243 回答
0

该 func_siftup在 heapq 源代码中进行了优化，这种实现方式只是将较小的孩子冒泡直到碰到叶子，然后 _siftdown finnaly可以比正常方式减少比较的次数（只是_siftup每次都比较 parent 与 left_child，right_child） .

于 2020-07-29T03:21:40.540 回答