python heapq源代码_siftdown

Question

PYTHON：

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 cmp_lt(newitem, parent):
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

我刚刚查看了 heapq 源代码，谁能解释一下第 6 行的作用？什么是 >> 运算符以及它是如何工作的？

Answer 1

该>>操作装置按位右移。将（非负整数）右移一位相当于除以二并向下舍入。换句话说，spam >> 1和spam // 2是一样的。

那么，为什么要使用>>？某些 CPU（尤其是较旧的 CPU）可以比除法快几个数量级的位移。大多数现代C编译器将优化n / 2到n >> 1适当的时候，但旧的不会。当然，这在 Python 中几乎没有区别，但是大多数传统的堆实现（您将在数据结构教科书中看到的类型）将使用>>. 最重要的是，对于某些人（从那些教科书中学到的那种人），>>算法是一个很好的信号，表明它是对数的。

所以这一parentpos = (pos-1) >> 1行试图返回其父级的索引。但为什么是负 1？假设当前索引是 4，这是树的第三层，然后你减 1 得到 3。二进制数是 11，如果你向右移动一个，那么它会是索引 1，它不是父索引。

阅读文档的顶部：

此实现使用数组，其中heap[k] <= heap[2*k+1]和heap[k] <= heap[2*k+2]所有k...

所以，对于k=1，孩子是2*1+1 = 3和2*1+2 = 4。正如下一段所指出的，这可能会令人困惑：

下面的 API 在两个方面不同于教科书的堆算法： (a) 我们使用从零开始的索引。这使得节点的索引与其子节点的索引之间的关系稍微不那么明显，但更合适，因为 Python 使用从零开始的索引。

所以，你期望的孩子1是2和3，但如果你在基于0的角度来考虑的话，你应该期待的是的孩子0是1和2，和孩子们1都3和4。