Heapq模块实现 [英] Heapq module implementation

问题描述

我正在阅读 heapq 模块源，因为我在<一个href ="https://codereview.stackexchange.com/"> CodeReview ，我听不懂.

I was reading the heapq module source because I reviewed a question on CodeReview and I cannot understand something.

在维基百科文章中，有关堆的内容是:

In the wikipedia article about heap it says:

筛选:根据需要在树中上移一个节点；用于在插入后恢复堆条件.称为筛分".因为节点会像筛子一样向上移动树直到达到正确的水平.

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 (如果我没看错维基百科，那么在插入一个元素时，我希望看到一个 siftup 调用，而不是一个 siftdown 调用.

If I read wikipedia right, when inserting an element I was expecting to see a siftup call, not a siftdown one.

类似于 heappop (来源):

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

在Wikipedia文章中，我希望进行一次 siftdown 调用，但是得到了 siftup 一条.

From the wikipedia article I was expecting a siftdown call but got a siftup one.

在Wikipedia中还是在 heapq 模块上是错误的?还是我的理解错了?

Is it a mistake in Wikipedia or on the heapq module? Or is my understand wrong?

推荐答案

如注释中所述，这是一个命名问题.最常见的术语将根称为树的顶部"，而其他级别的节点则位于根的下方".我们以该方向绘制树.那就是:

As noted in comments, it's a nomenclature issue. The most common terminology calls the root the "top" of the tree, and nodes at other levels are "below" the root. We draw the tree in that orientation. That is:

        1
    2       3
  4   5   6   7

那么，说将项目从根目录移到较低级别是向下筛选".

It makes sense, then, to say that to move an item from the root to a lower level is "sifting down."

您可以像有人在评论中所做的那样，提出一个论点，即将某事物移至较低级别将增加其在后备数组中的索引，因此将其称为筛选"是有道理的.但是人们正在可视化树模型，而不是数组实现.说到模型时，您的术语应与模型一致.

You could make the argument, as somebody did in comments, that moving something to a lower level is increasing its index in the backing array, so it makes sense to speak of that as "sifting up". But people are visualizing the tree model, not the array implementation. When speaking of the model, your terminology should be consistent with the model.

我总是觉得有点烦， heapq 的作者决定使用非标准术语.有人可能会说他在谈论实施，但我对此表示怀疑.注释中说:提速:在树中向上移动节点……"显然，他指的是树模型.

I've always found it a bit annoying that the author of heapq decided to use the non-standard terminology. One could argue that he's talking about the implementation, but I dispute that. The comment says, "sift-up: move a node up in the tree ..." Clearly, he's referring to the tree model.

Wikipedia， https://en.wikipedia.org/wiki/Tree_structure 说:

Wikipedia, https://en.wikipedia.org/wiki/Tree_structure, says:

树形结构或树形图是一种以图形形式表示结构的层次结构性质的方法.之所以称为树结构"，是因为经典表示类似于树，即使图表与实际树相比通常是倒置的，根"位于顶部，叶"位于底部.

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-在现实生活中.

This topic was discussed to death in the early days, perhaps most famously by Donald Knuth in The Art of Computer Programming. See https://www.quora.com/Why-are-trees-in-computer-science-generally-drawn-upside-down-from-how-trees-are-in-real-life.

这篇关于Heapq模块实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！