擅长:python、mysql、java
<p>堆中的每个节点都比其所有子节点大。另外,如果节点位于索引i,则其直接子节点位于索引2*i+1和2*i+2处。</p>
<p>将堆视为二叉树,可以向下递归堆,如果某个条目大于所获得的maxkey(因为它的所有子项都将更大),如果节点的键在minkey和maxkey之间,则输出该节点。</p>
<p>把这些放在一起可以得到:</p>
<pre><code>def extract_range(h, i, minkey, maxkey):
if i >= len(h) or h[i][0] >= maxkey:
return
if h[i][0] >= minkey:
yield h[i]
for k in 1, 2:
for r in extract_range(h, 2 * i + k, minkey, maxkey):
yield r
</code></pre>