heapq — 힙 큐 알고리즘
heapq — 힙 큐 알고리즘
heapq 모듈은 힙 큐 알고리즘(우선순위 큐 알고리즘)의 구현을 제공해요.
최소 힙(min-heap)은 모든 부모 노드가 자식 중 어느 것보다 작거나 같은 값을 갖는 이진 트리예요. 이 조건을 힙 불변식(heap invariant)이라 불러요. 최소 힙의 경우 이 구현은 heap[k] <= heap[2*k+1]이고 heap[k] <= heap[2*k+2]인 리스트를 사용해요(비교 요소가 존재하는 모든 k에 대해). 요소는 0부터 세어요. 최소 힙의 흥미로운 속성은 가장 작은 요소가 항상 루트, 즉 heap[0]이라는 것이에요.
최대 힙(max-heap)은 역 불변식을 만족해요. maxheap[2*k+1] <= maxheap[k]이고 maxheap[2*k+2] <= maxheap[k]인 리스트로 구현되며, 루트 maxheap[0]이 가장 큰 요소를 포함해요. heap.sort(reverse=True)는 최대 힙 불변식을 유지해요.
heapq API는 교과서의 힙 알고리즘과 두 가지 면에서 달라요: (a) 0 기반 인덱싱을 사용하고, (b) 교과서는 제자리 정렬에 적합한 최대 힙에 초점을 두지만, 이 구현은 파이썬 list에 더 잘 대응하는 최소 힙을 선호해요. 이 두 가지 면 덕분에 힙을 놀라움 없이 일반 파이썬 리스트로 볼 수 있어요. heap[0]은 가장 작은 항목이고, heap.sort()는 힙 불변식을 유지해요.
list.sort()처럼 이 구현은 최소 힙과 최대 힙 모두에 대해 비교에 < 연산자만 사용해요. 아래 API에서 수식어 없는 힙은 일반적으로 최소 힙을 가리키고, 최대 힙 API는 _max 접미사로 이름이 지어져요.
힙을 만들려면 []로 초기화된 리스트를 사용하거나, 기존 리스트를 heapify() 또는 heapify_max() 함수를 사용해 각각 최소 힙이나 최대 힙으로 변환해요.
본문
최소 힙 함수
heapq.heapify(x) — 리스트 x를 제자리에서 선형 시간에 최소 힙으로 변환해요.
heapq.heappush(heap, item) — 최소 힙 불변식을 유지하며 힙에 값 item을 푸시해요.
heapq.heappop(heap) — 힙에서 가장 작은 항목을 팝하고 최소 힙 불변식을 유지하며 반환해요. 힙이 비어 있으면 IndexError가 발생해요. 팝하지 않고 가장 작은 항목에 접근하려면 heap[0]을 사용해요.
heapq.heappushpop(heap, item) — 힙에 item을 푸시한 다음 힙에서 가장 작은 항목을 팝해 반환해요. 결합된 동작은 heappush() 후 별도의 heappop() 호출보다 더 효율적이에요.
heapq.heapreplace(heap, item) — 힙에서 가장 작은 항목을 팝해 반환하고 새 항목도 푸시해요. 힙 크기는 변하지 않아요. 힙이 비어 있으면 IndexError가 발생해요. 이 한 단계 연산은 heappop() 후 heappush()보다 효율적이며, 고정 크기 힙을 사용할 때 더 적합할 수 있어요. 반환되는 값은 추가된 항목보다 클 수 있어요. 그게 원하지 않으면 heappushpop()을 고려해요.
최대 힙 함수
heapq.heapify_max(x) — 리스트 x를 제자리에서 선형 시간에 최대 힙으로 변환해요. 버전 3.14에서 추가됨.
heapq.heappush_max(heap, item) — 최대 힙 불변식을 유지하며 최대 힙 heap에 값 item을 푸시해요. 버전 3.14에서 추가됨.
heapq.heappop_max(heap) — 최대 힙 heap에서 가장 큰 항목을 팝해 최대 힙 불변식을 유지하며 반환해요. 최대 힙이 비어 있으면 IndexError가 발생해요. 팝하지 않고 가장 큰 항목에 접근하려면 maxheap[0]을 사용해요. 버전 3.14에서 추가됨.
heapq.heappushpop_max(heap, item) — 최대 힙 heap에 item을 푸시한 다음 가장 큰 항목을 팝해 반환해요. 버전 3.14에서 추가됨.
heapq.heapreplace_max(heap, item) — 최대 힙 heap에서 가장 큰 항목을 팝해 반환하고 새 항목을 푸시해요. 버전 3.14에서 추가됨.
일반 목적 함수
heapq.merge(*iterables, key=None, reverse=False) — 여러 정렬된 입력을 하나의 정렬된 출력으로 병합해요(예: 여러 로그 파일의 타임스탬프 항목 병합). 정렬된 값에 대한 이터레이터를 반환해요. sorted(itertools.chain(*iterables))와 비슷하지만 iterable을 반환하고 데이터를 한 번에 메모리로 가져오지 않으며, 각 입력 스트림이 이미 정렬되어 있다고 가정해요.
heapq.nlargest(n, iterable, key=None) — iterable로 정의된 데이터셋에서 가장 큰 n개 요소의 리스트를 반환해요. sorted(iterable, key=key, reverse=True)[:n]과 동일해요.
heapq.nsmallest(n, iterable, key=None) — iterable로 정의된 데이터셋에서 가장 작은 n개 요소의 리스트를 반환해요. sorted(iterable, key=key)[:n]과 동일해요.
후자 두 함수는 n이 작을 때 가장 잘 동작해요. 큰 값에는 sorted() 함수를 사용하는 것이 더 효율적이에요. 또한 n==1일 때는 내장 min()과 max() 함수를 사용하는 것이 더 효율적이에요.
기본 예시
힙 정렬(heapsort)은 모든 값을 힙에 푸시한 다음 가장 작은 값을 하나씩 팝해서 구현할 수 있어요:
>>> def heapsort(iterable):
... h = []
... for value in iterable:
... heappush(h, value)
... return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
힙 요소는 튜플일 수 있어요. 이는 추적 중인 기본 레코드와 함께(작업 우선순위 같은) 비교 값을 할당하는 데 유용해요:
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (1, 'write spec'))
>>> heappop(h)
(1, 'write spec')
우선순위 큐 구현 참고 사항
우선순위 큐는 힙의 일반적인 용도이며 여러 구현 과제를 제시해요:
- 정렬 안정성: 우선순위가 같은 두 작업을 원래 추가된 순서로 어떻게 반환할까?
- 튜플 비교는 우선순위가 같고 작업에 기본 비교 순서가 없으면
(priority, task)쌍에서 깨져요. - 작업의 우선순위가 바뀌면 힙의 새 위치로 어떻게 이동할까?
- 보류 중인 작업을 삭제해야 한다면 어떻게 찾아 큐에서 제거할까?
처음 두 과제의 해결책은 우선순위, 항목 카운트, 작업을 포함하는 3요소 리스트로 항목을 저장하는 것이에요. 항목 카운트가 동점자(tie-breaker) 역할을 해 같은 우선순위를 가진 두 작업이 추가된 순서대로 반환돼요. 비교 불가능한 작업 문제의 또 다른 해결책은 작업 항목을 무시하고 우선순위 필드만 비교하는 래퍼 클래스를 만드는 것이에요.
이론
힙은 a[k] <= a[2*k+1]이고 a[k] <= a[2*k+2]인 배열이에요(0부터 요소를 세고, 존재하지 않는 요소는 무한대로 간주). 힙의 흥미로운 속성은 a[0]이 항상 가장 작은 요소라는 것이에요. 위의 이상한 불변식은 토너먼트를 위한 효율적인 메모리 표현을 의미해요.
힙은 종종 이벤트를 스케줄링하는 스케줄러 구현에 좋은 구조예요. 또한 큰 디스크 정렬에서도 매우 유용한데, 초기 정렬이 가능한 한 가장 긴 “run”을 생성하는 것이 중요하고 토너먼트가 이를 달성하는 좋은 방법이기 때문이에요.