[Python]파이썬 heapq 이해하기 (최소힙)

 

heapq의 원리:

 

heapq는 heapq연산을 해야만 힙의 구조가 깨지지 않는다. 

(만약, heapq를 직접 수정하면(인덱스를 통해 값 변경) 힙의 구조가 깨진다. )

 

heapq연산에는 heappush, heappop 등이 있다. 

 

heapq는 heapq연산을 수행하고 나서 자체적으로 정렬을 할 때, 남은 리스트 전체를 정렬하는 것이 아니라, 필요한 최소한의 연산만 한다. 

결과적으로 해당 heapq에서 최소값만을 맨 앞에 놓는다.

 

이런식으로 heapq는 항상 첫 번째 값이 최소값이 되도록 관리한다. 해당 과정은 이진 트리의 형태를 유지하면서, 최소한의 요소 이동만으로 이루어지기 때문에 효율적이다.

 

이것이 최소힙의 구조이다. 

 

heapq 사용예시:

 

import heapq

n, m = map(int, input().split())
tmp = list(map(int, input().split()))

heapq.heapify(tmp)

for i in range(m):
    # 최소값 두 개 꺼내기
    smallest1 = heapq.heappop(tmp)
    smallest2 = heapq.heappop(tmp)
    
    # 두 값을 합친 후 다시 삽입
    summ = smallest1 + smallest2
    heapq.heappush(tmp, summ)
    heapq.heappush(tmp, summ)
    
print(sum(tmp))

 

 

이를 이해하기 최소힙을 이해하기 좋은 백준 문제 

: 15903 카드 합체 놀이(https://www.acmicpc.net/problem/15903)