python heapq源代码

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

我能解释一下6号源代码吗？什么是运算符及其工作原理？在

Answer 1

>>运算符表示bitwise right shift。将（非负整数）右移一位相当于除以2并向下取整。换句话说，spam >> 1和{}是相同的。在

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

---

so this parentpos = (pos-1) >> 1 line is trying to return the index of its parent. But why minus 1? Say the current index is 4 which is the third level of the tree, and then you minus 1 get 3. And the binary number is 11, if you shift one right then it will be index 1, and its not the parent index.

阅读the documentation的顶部：

This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k…

因此，对于k=1，子元素是2*1+1 = 3和{}。正如下一段所述，这可能会令人困惑：

The API below differs from textbook heap algorithms in two aspects: (a) We use zero-based indexing. This makes the relationship between the index for a node and the indexes for its children slightly less obvious, but is more suitable since Python uses zero-based indexing.

因此，您期望1的子元素是2和{}，但是如果您用基于0的术语来考虑它，您应该期望0的子元素是{}和{}，而{}的子元素是{}和{}。在

Answer 2

>>是右移位运算符。它删除最右边的位，这与除以2并忽略余数相同。所以这行可能是parentpos = (pos - 1) // 2。在

Python的堆是从零开始的，因此节点i在2 * i + 1和{}处有子节点。它的父节点位于(i - 1) // 2。在

siftdown的作用是向上移动一个值（通过与父对象交换），直到父对象小于子对象。在