python - Heapq模块实现

Question

我正在阅读 heapq 模块源代码，因为我查看了 question上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

正如评论中所指出的，这是一个命名问题。最常见的术语将根称为树的“顶部”，其他级别的节点位于根的“下方”。我们以那个方向绘制树。即:

        1
    2       3
  4   5   6   7

因此，将项目从根移动到较低级别是“向下筛选”，这是有道理的。

您可以提出论点，就像有人在评论中所做的那样，将某些内容移动到较低级别会增加其在支持数组中的索引，因此将其称为“筛选”是有意义的。但人们正在可视化树模型，而不是数组实现。当谈到模型时，你的术语应该与模型一致。

我一直觉得 heapq 的作者决定使用非标准术语有点烦人。有人可能会说他正在谈论实现，但我对此提出异议。评论说，“sift-up:在树中向上移动一个节点......”显然，他指的是树模型。

维基百科，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 .