从heapq中提取元素的Pythonic方式

Question

我正在使用一个优先队列（heapq），其中的优先级是基于datetime.datetime的。

如果我有一个开始时间和结束时间，想从这个列表中提取一部分元素，最符合Python风格的方法是什么？（我不能修改原始列表，所以我必须创建一个新列表并返回，或者返回一个迭代器）

下面是我所拥有的一个例子：

>>> import heapq
>>> timeLine = []
>>> from datetime import datetime
>>> heapq.heappush(timeLine, (datetime.now(),'A'))
>>> heapq.heappush(timeLine, (datetime.now(),'B'))
>>> heapq.heappush(timeLine, (datetime.now(),'C'))
>>> timeLine
[(datetime.datetime(2013, 2, 8, 15, 25, 14, 720000), 'A'), (datetime.datetime(2013, 2, 8, 15, 25, 30, 575000), 'B'), (datetime.datetime(2013, 2, 8, 15, 25, 36, 959000), 'C')]

实际应用中的列表非常庞大。

Answer 1

在一个堆中，每个节点的值都比它的所有子节点的值要大。而且，如果这个节点在索引 i 的位置，它的直接子节点会在索引 2 * i + 1 和 2 * i + 2 的位置。

把堆看作一棵二叉树，你可以从上往下递归遍历这个堆。如果遇到一个节点的值比你手里的最大值 maxkey 还要大，就可以停止了，因为它的所有子节点的值肯定也会更大。如果一个节点的值在你手里的最小值 minkey 和最大值 maxkey 之间，就可以把这个节点输出。

把这些内容结合起来，就得到了：

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

Answer 2

堆这种数据结构并不是执行这个操作的最佳选择。如果你按照 heapq 的公开接口来使用，堆会被改变，这样就没法再进行其他操作了。@Anonymous 提出的解决方案可能有效，但我觉得它太依赖于具体的实现细节。虽然这些细节是公开的，但我不确定你是否真的应该这样使用它们。

一个简单的方法是先对列表进行排序，然后进行两次二分查找，这样就能实现你想要的功能：

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]

这个方法唯一的问题是，最坏情况下排序需要 O(n lg n) 的时间，但你用来构建堆的方式（heapq.heapify 也需要线性时间）也是如此。