从heapq中提取元素的Python法

Question

我正在使用一个优先级为datetime.datetime的优先级队列（heapq）。在

如果我有startTime和endTime可以搜索，那么从这个列表中提取元素子集的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的公共API，则堆将被更改，使其无法用于进一步的操作。@“匿名”解决方案可能会奏效，但（IMHO）过于依赖实现细节。虽然这些都是公开记录，但我不确定你是否真的应该使用它们。

简单地对列表进行排序并执行两个二进制搜索是一种简单的方法：

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（nlgn）时间，但是构建堆的方法也需要时间（heapq.heapify将需要线性时间）。