Heapq模块实现

Question

我正在阅读 heapq 模块源代码，因为我查看了一个 question on CodeReview 但我无法理解某些内容。

在关于堆的 wikipedia article 中说：

sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve.

sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.

但是heappush（source code）的代码是：

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

如果我没看错维基百科，在插入元素时，我希望看到 siftup 调用，而不是 siftdown 调用。

与 heappop (source here) 类似：

def heappop(heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
return lastelt

根据维基百科文章，我期待 siftdown 来电，但接到了 siftup 来电。

维基百科或 heapq 模块中的错误吗？还是我理解有误？

Answer 1

如评论中所述，这是一个命名问题。最常见的术语称根为树的 "top"，其他级别的节点为 "below" 根。我们以那个方向画树。即：

        1
    2       3
  4   5   6   7

那么，将项目从根移动到较低级别是有道理的 "sifting down."

您可以像评论中的某人那样提出论点，将某些内容移至较低级别会增加其在后备数组中的索引，因此将其称为 "sifting up" 是有道理的。但是人们正在可视化树模型，而不是数组实现。谈到模型时，您的术语应该与模型保持一致。

我一直觉得 heapq 的作者决定使用非标准术语有点烦人。有人可能会争辩说他是在谈论实施，但我对此表示异议。评论说，"sift-up: move a node up in the tree ..." 显然，他指的是树模型。

维基百科，https://en.wikipedia.org/wiki/Tree_structure，说：

A tree structure or tree diagram is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the "leaves" at the bottom.

这个话题在早期被讨论到死，也许最著名的是 Donald Knuth 在 计算机编程的艺术 中。参见 https://www.quora.com/Why-are-trees-in-computer-science-generally-drawn-upside-down-from-how-trees-are-in-real-life。

Heapq模块实现

Heapq module implementation

python

algorithm

heap

standard-library

data-structures