heapq

• heapq 모듈은 이진 트리 기반의 최소 힙(min heap) 자료구조를 제공한다. (자바의 PriorityQueue 클래스와 비슷)
  • ✍ 최소 힙 : heapq.pop() 메소드는 힙 원소중 가장 작은 항목을 반환한다.

heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]

• 최소 힙 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2)보다 크기가 작거나 같도록 원소가 추가되고 삭제된다.

heapq 메소드

✋모듈 import

import heapq

✋최소 힙 생성

heap = []

• 빈 리스트 heap을 생성한뒤 heapq 모듈의 함수를 호출할 때 마다 heap 리스트를 인자로 넘겨야 한다.
  👉 heap 모듈을 통해 원소를 추가, 삭제한 리스트가 최소 힙이다.

✋heappush(heap, item)

• 힙 불변성을 유지하면서, item 값을 heap으로 푸시
• • heappush() 함수는 O(logN)의 시간 복잡도를 가진다

heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print(heap) # [1, 3, 7, 4]

✋heappop(heap)

• 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 pop하고 반환
• pop 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용

print(heapq.heappop(heap)) # 1
print(heap) # [3, 4, 7]

print(heapq.heappop(heap)) # 3
print(heap) # [4, 7]

## 최솟값 삭제하지 않고 얻기
print(heap[0]) # 4

✋heapify(x)

• 리스트 x를 선형 시간으로 제자리에서 힙으로 변환
• O(N)의 시간 복잡도를 가짐

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap) # [1, 3, 5, 4, 8, 7]

✋heappushpop(heap, item)

• 힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 pop하고 반환
• heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적

✋heapreplace(heap, item)

• heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시
• heappop()한 다음 heappush()하는 것보다 더 효율적
• 고정 크기 힙을 사용할 때 더 적합하다

✋nlargest(n, iterable, key=None)

• n 개의 가장 큰 요소로 구성된 리스트를 반환

✋nsmallest(n, iterable, key=None)

• n 개의 가장 작은 요소로 구성된 리스트를 반환

---

• 참고자료
  • heapq --- 힙 큐 알고리즘
  • [파이썬] heapq 모듈 사용법