[Python] heapq 모듈

 

힙 자료구조

 

heapq 모듈은 이진트리 기반의 최소힙(min heap) 자료구조를 제공한다.

 

min heap을 이용하면 원소들이 항상 정렬된 상태로 추가되고 삭제된다.

min heap에서 가장 작은 값은 언제나 인덱스 0이고,

내부적으로 min heap 내의 모든 원소는 항상 자식 원소(k)는

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

 

 

모듈 임포트

import heapq

내장 모듈이라, 파이썬만 설치되어 있다면 간단하게 임포트 후 힙 관련 함수 사용 가능

 

힙에 원소 추가

heap = []
heapq.heappush(heap,4)
# heapq.heappush(추가할 리스트 대상, 추가할 원소)

 

힙에서 원소 삭제

heapq.heappop(head)
# 가장 작은 원소를 삭제 후 그 값을 리턴

 

최소값 삭제하지 않고 얻을 때는 리스트 처럼 인덱스를 통해 접근 가능

print(heap[0])

 

기존 리스트를 힙으로 변환

 

heapq.heapify(heap)

heapify()함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 위에서 다룬 힙 구조에 맞게 재배치되며 초치소 값이 0번째 인덱스에 위치하게 된다. 성능은 인자로 넘기는 리스트의 원소수에 비례. 즉 O(N)의 시간 복잡도를 가짐.