<p><code>>></code>运算符表示<a href="https://docs.python.org/2/library/stdtypes.html#bitwise-operations-on-integer-types" rel="nofollow">bitwise right shift</a>。将(非负整数)右移一位相当于除以2并向下取整。换句话说,<code>spam >> 1</code>和{<cd3>}是相同的。在</p>
<p>那么,为什么要使用<code>>></code>?一些CPU,尤其是较老的CPU,可以比除法更快地进行数量级的位移位。大多数现代的C编译器会在适当的时候将<code>n / 2</code>优化为<code>n >> 1</code>,但是旧的编译器不会。当然,这在Python中几乎没有什么区别,但是大多数传统的堆实现(您在数据结构教科书中看到的类型)将使用<code>>></code>。除此之外,对于某些人(从教科书中学习到的那种人),算法中的<code>>></code>是一个很好的信号,表明它是对数的。在</p>
<hr/>
<blockquote>
<p>so this <code>parentpos = (pos-1) >> 1</code> 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. </p>
</blockquote>
<p>阅读<a href="https://docs.python.org/3/library/heapq.html" rel="nofollow">the documentation</a>的顶部:</p>
<blockquote>
<p>This implementation uses arrays for which <code>heap[k] <= heap[2*k+1]</code> and <code>heap[k] <= heap[2*k+2]</code> for all <code>k</code>…</p>
</blockquote>
<p>因此,对于<code>k=1</code>,子元素是<code>2*1+1 = 3</code>和{<cd11>}。正如下一段所述,这可能会令人困惑:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>因此,您期望<code>1</code>的子元素是<code>2</code>和{<cd14>},但是如果您用基于0的术语来考虑它,您应该期望<code>0</code>的子元素是{<cd12>}和{<cd13>},而{<cd12>}的子元素是{<cd14>}和{<cd20>}。在</p>