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

>> 是一个右移运算符。它的作用是把最右边的那一位去掉，这就相当于把一个数除以二，然后不考虑余数。所以那行代码其实可以写成 parentpos = (pos - 1) // 2。

在Python中，堆是从零开始编号的，也就是说，一个节点 i 的孩子节点分别在 2 * i + 1 和 2 * i + 2 这两个位置。而它的父节点则在 (i - 1) // 2 的位置。

siftdown 的作用是把一个值向上移动（通过和它的父节点交换位置），直到父节点的值小于这个孩子节点的值为止。

Answer 2

这个 >> 操作符表示的是 按位右移。把一个非负整数右移一位，相当于把这个数除以二并向下取整。换句话说，spam >> 1 和 spam // 2 是一样的。

那么，为什么要用 >> 呢？一些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 的孩子是 1 和 2，而 1 的孩子是 3 和 4。