라이브러리 heap] 기초 개념, 함수
개념
힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리
이 구현에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용
요소는 0부터 count
비교를 위해, 존재하지 않는 요소는 무한으로 간주
가장 작은 요소는 항상 루트인 heap[0]
함수
1] 힙 불변성을 유지하면서, item 값을 heap으로 푸시
heapq.heappush(heap, item)
2] 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환
ㆍ 힙이 비어 있으면, IndexError가 발생
ㆍ pop 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용
heapq.heappop(heap)
3] 힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 pop하고 반환
ㆍ 결합한 액션은 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행
heapq.heappushpop(heap, item)
4] 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.
heapq.heapify(x)
5] heap에서 가장 작은 항목을 팝하고 반환, 새로운 item도 푸시
ㆍ 힙 크기는 변경되지 않는다.
ㆍ 힙이 비어 있으면, IndexError가 발생
heapq.heapreplace(heap, item)
6] 여러 정렬된 입력을 단일 정렬된 출력으로 병합 (예를 들어, 여러 로그 파일에서 타임 스탬프 된 항목을 병합).
ㆍ 정렬된 값에 대한 이터레이터를 반환
heapq.merge(*iterables, key=None, reverse=False)