擅长:python、mysql、java
<p>堆不是执行此操作的理想结构;如果坚持使用<code>heapq</code>的公共API,则堆将被更改,使其无法用于进一步的操作。@“匿名”解决方案可能会奏效,但(IMHO)过于依赖实现细节。虽然这些都是公开记录,但我不确定你是否真的应该使用它们。</p>
<p>简单地对列表进行排序并执行两个二进制搜索是一种简单的方法:</p>
<pre><code>from bisect import bisect_left, bisect_right
def find_range(timeline, start, end):
l = bisect_left(timeline, start)
r = bisect_right(timeline, end)
for i in xrange(l, r):
yield timeline[i]
</code></pre>
<p>这种方法唯一的问题是排序在最坏的情况下需要O(<em>n</em>lg<em>n</em>)时间,但是构建堆的方法也需要时间(<code>heapq.heapify</code>将需要线性时间)。</p>