为什么_siftup 和_siftdown 在Python 中刚好相反？

Question

根据维基百科binary heap的定义， sift-up又称为up-heap运算，sift-down称为down-heap.

所以在堆（完全二叉树）中，up表示从叶子到根，down表示从根到叶子。

但在python中，似乎正好相反。我对 siftup 和 siftdown 的含义感到困惑，并且在我第一次使用时被误用。

这里是 heapq 中 _siftdown 和 _siftup 的 python 版本实现：

# 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
# is the index of a leaf with a possibly out-of-order value.  Restore the
# 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
    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)

为什么在python中相反？我已经在 wiki 和其他几篇文章中确认过。我有什么遗漏或误解吗？

感谢阅读，非常感谢它能帮助我。 :)

Answer 1

查看维基百科页面上的参考资料，我发现了这一点：

Note that this paper uses Floyd's original terminology "siftup" for what is now called sifting down.

似乎不同的作者对"up"和"down"有不同的参考。

但是，正如@Dan D 在评论中所写，无论如何您都不应该使用这些功能。

为什么_siftup 和_siftdown 在Python 中刚好相反？

Why is _siftup and _siftdown just the opposite in Python?

python

heap

heapq