파이썬의 heapq는 **최소 힙(min-heap)**을 기본으로 제공하며, 이를 통해 최솟값을 빠르게 조회하고 삭제하는 것이 가능합니다. 각 연산의 시간 복잡도와 함께 주요 연산에 대해 설명드리겠습니다. 최대 힙을 구현하기 위해서는 입력값과 출력값에 -1을 곱하여 문제를 해결할 수 있다.

• 본 페이지는 자료구조 우선순위 큐에 대해 다루는 페이지 입니다. 자료구조 우선순위 큐에 대한 내용은 아래 페이지를 참고 하길 바랍니다.

  Priority Heap

주요 함수

heapq.heappush(heap, item), 삽입 연산

• 설명: 힙에 새로운 요소 item을 추가합니다. 이때 힙 구조가 유지되도록 삽입합니다.
• 동작 방식: 새로운 요소를 힙의 마지막에 추가한 후, 부모 노드와 비교하며 위로 올라가서(최소 힙 기준) 제자리를 찾습니다.
• 시간 복잡도: O(log N) (N은 힙의 요소 수)

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heap)  # [1, 10, 5]

heapq.heappop(heap), 제거 연산

• 설명: 힙에서 가장 작은 요소(루트 노드)를 제거하고 반환합니다. 삭제 후 힙 구조가 유지되도록 재정렬합니다.
• 동작 방식: 힙의 첫 요소(최소값)를 제거한 후, 마지막 요소를 루트 노드로 이동시키고 자식 노드와 비교하면서 아래로 내려갑니다(최소 힙 기준).
• 시간 복잡도: O(log N)

smallest = heapq.heappop(heap)
print(smallest)  # 1
print(heap)  # [5, 10]

heapq.heappushpop(heap, item), 삽입후 제거 연산

• 설명: 힙에 새로운 요소 item을 삽입한 뒤, 가장 작은 요소를 제거하고 반환합니다. 이 연산은 heappush와 heappop을 연속으로 호출하는 것보다 더 효율적입니다. ⇒ 다른 함수 2개를 사용하는 것보다 해당 함수 1개를 사용하는 것이 효율적
• 시간 복잡도: O(log N)

smallest = heapq.heappushpop(heap, 2)
print(smallest)  # 1
print(heap)  # [2, 3, 4, 9, 5]

heapq.heapreplace(heap, item), 제거후 삽입 연산

• 설명: 힙에서 가장 작은 요소를 제거하고, 새로운 요소 item을 삽입합니다. 이 연산도 heappop과 heappush를 연속으로 호출하는 것보다 더 효율적입니다.