siftdown 函数的实现违反了堆的正式定义？

Question

我现在正试图了解堆的实现，我研究了 python 的 heapq 模块。
https://github.com/python-git/python/blob/master/Lib/heapq.py
Line236 是 siftdown 代码的开始，奇怪的是，它对我来说看起来像一个 siftup，因为它在堆数组的最后一个元素上添加了一个 newitem 并试图将最后一个元素向上移动到它的正确位置。

while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break

它将当前位置的索引减少到(pos-1)//2，最后pos可能会转到索引0。所以这对我来说就像一个筛选。我是不是误会了什么？

Answer 1

这只是术语冲突。他们所说的 "siftup" 是向树叶筛选。也许想法是在最小堆中，较大的项目 "up" 移向叶子。

他们"siftdown"向根移动。

它与我们计算机人员通常（？）认为的树相反，但它是一致的。如果你想象一棵实体树，这是有道理的——生长在院子里的东西，在秋天落下的叶子，我必须耙起来处理。

siftdown 函数的实现违反了堆的正式定义？

implement of siftdown function violates heap formal definition?

python

heap