힙에서 요소를 추출하는 Python 방법

Question

우선 순위 큐 (heapq)의 (datetime.datetime)을 우선 순위로 사용하고 있습니다.

검색 할 startTime 및 endTime이있는 경우이 목록에서 요소의 하위 집합을 추출하는 가장 비범 한 방법은 무엇입니까?

>>> 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의 공개 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] 

이 방법에 대한 유일한 문제는 그 분류는 (LG NN) O합니다 시간이 최악의 경우이지만 힙을 생성하는 방법도 마찬가지입니다 (heapq.heapify은 선형 시간이 걸립니다).

Answer 2

힙의 모든 노드가 모든 자식 노드보다 큽니다. 또한 노드가 인덱스 i에있는 경우, 해당 직계 하위 노드는 인덱스 2 * i + 1 및 2 * i + 2에 있습니다.

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