heapq 모듈

heapq 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현을 제공합니다.

힙(heap)을 잠깐 살펴보자면...🐥

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며, 완전 이진 트리 기반의 자료구조이다.
• 힙의 종류로 최대 힙과 최소 힙이 있는데 heapq 모듈은 최소 힙이다.
• 힙을 이용하여 우선순위 큐를 구현할 수 있다.

✅ 모듈 import 하기

from heapq import *

✅ 최소 힙 생성하기

초기화된 리스트를 사용하여 힙을 생성합니다.

heap = []

✅ 힙에 원소 추가하기

item 값을 heap으로 푸시합니다.

heappush(heap, item)

👉 시간복잡도는 O(logn) 입니다.

✅ 힙에서 원소 제거하기

heap에서 가장 작은 항목을 팝하고 반환합니다.

heappop(heap)

밑의 예제를 보면 가장 작은 원소인 1부터 차례대로 pop 되고 있습니다.

from heapq import *

heap = []

heappush(heap, 3)   # 삽입
heappush(heap, 5)   # 삽입
heappush(heap, 1)   # 삽입
heappop(heap)  # 삭제
heappop(heap)  # 삭제
heappop(heap)  # 삭제

# Output
1
3
5

👉 시간복잡도는 O(logn) 입니다.

✅ pop 하지 않고 최솟값 얻기

원소를 삭제하지 않고 최솟값을 읽고 싶다면 heap 리스트의 0번째 인덱스로 접근하면 됩니다. 이 구현에서는 가장 작은 요소가 항상 루트인 heap[0]이라는 것입니다.

heap[0]

✅ push 하고 pop 하기

힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환합니다. 따라서 두 값 중 큰 값만 힙에 남겨 둡니다.

heappushpop(heap, item)

❗️ 이 연산는 heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적으로 실행합니다.

✅ pop 하고 push 하기

heap에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시합니다.

heapq.heapreplace(heap, item)

❗️ 이 연산은 heappop()한 다음 heappush()하는 것보다 더 효율적입니다.

✅ 리스트를 힙으로 변환하기

값이 들어있는 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

heapify(x)

heap = [7, 4, 1, 5, 6, 2]
heapify(heap)

print(heappop(heap))    # 삭제
print(heappop(heap))    # 삭제

# Output
1
2

👉 리스트 x의 크기를 n이라고 했을 때, O(n)의 시간복잡도를 가집니다.

🌈 최대 힙 사용하기

만약 최소 힙이 아닌 최대 힙으로 사용하고 싶다면?! 원소를 삽입/삭제하는 경우에 원소에다 -1을 곱하면 됩니다.

아래 예제로 살펴보겠습니다. 3, 5, 1을 차례대로 heap에 추가해줍니다. 이때 -1를 곱한 채로 heap에 넣고, heap에서 꺼낼 때도 -1을 곱해서 꺼냅니다. 그러면 출력 결과와 같이 최대 힙으로 사용할 수 있습니다.

heap = []

heappush(heap, -3)
heappush(heap, -5)
heappush(heap, -1)
print(-heappop(heap))
print(-heappop(heap))

# Output
5
3

Reference
https://docs.python.org/ko/3/library/heapq.html
https://www.daleseo.com/python-heapq