파이썬 heapq.heapreplace 동작 원리

파이썬 heapq.heapreplace 동작 원리

heapreplace는 파이썬의 heapq 모듈에서 제공하는 유용한 함수로, 힙의 최솟값을 제거하고 새로운 값을 넣은 뒤, 힙을 재정렬하여 항상 최소 힙(min heap)의 조건을 유지하는 함수다.

📌 기본 개념

heapreplace(heap, item)은 다음과 같은 동작을 한다:

1. 힙의 루트(가장 작은 값)를 제거한다.
2. 새로운 값을 루트 자리에 넣는다.
3. 힙 조건(부모 < 자식)을 만족하도록 재정렬한다.

📊 힙 구조 시각화 예제

다음은 heap = [1, 3, 5, 7, 9, 11]일 때 heapreplace(heap, 2)가 어떻게 작동하는지 단계별로 나타낸 것이다.

1️⃣ 초기 힙 구조

        1
       / \
      3   5
     / \   \
    7   9   11
  

2️⃣ 루트(1) 제거 후, 새로운 값(2) 삽입

        2
       / \
      3   5
     / \   \
    7   9   11
  

이 시점에서 힙 조건이 유지되지 않으므로 재정렬이 필요하다.

3️⃣ 힙 재정렬 (heapify)

최소 힙 규칙에 따라 자식 노드들과 비교하며 위치를 조정한다. 이 경우 이미 부모가 자식들보다 작으므로 구조는 유지된다.

✅ heapreplace vs heappop + heappush

• heapreplace: 두 연산이 동시에 일어나므로 더 빠름
• heappop + heappush: 두 번의 재정렬이 일어나 성능 저하 가능

🔍 실습 예제

import heapq

heap = [1, 3, 5, 7, 9, 11]
heapq.heapify(heap)

print("Before:", heap)
replaced = heapq.heapreplace(heap, 2)
print("Replaced:", replaced)
print("After:", heap)
  

📌 정리

• heapreplace는 최솟값 제거 + 새 값 삽입을 한 번에 처리
• 삽입할 값이 기존 최솟값보다 클 때 사용하면 효율적
• 시간 복잡도는 O(log n)

🛠 글 작성자: ChatGPT + 사용자