从 heapq 中提取元素的 Pythonic 方法

Question

我正在使用优先级队列 (heapq)，优先级为datetime.datetime。

如果我要搜索 startTime 和 endTime，从这个列表中提取元素子集的最 pythonic 方法是什么。(我无法更改原始列表，所以我必须创建一个新列表并返回，或者返回一个迭代器)

下面是我所拥有的示例:

>>> 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

堆不是执行此操作的理想结构；如果您坚持使用 heapq 的公共(public) API，堆将被更改并变得无法用于进一步的操作。 @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 将花费线性时间)。