[자료구조] 힙(Heapq) 파이썬 모듈 사용

힙은 Min Heap과 Max Heap으로 나눌 수 있다.

힙은 세 가지 특징을 가진다.

- Min Heap인 경우 루트노드가 항상 최소값, Max Heap인 경우 루트노드가 항상 최댓값을 가진다.

- Max Heap(Min) 내의 임의의 노드를 루트로 하는 서브트리 또한 Max Heap(Min)이다.

- 완전 이진 트리여야한다. 따라서 m 번 노드의 왼쪽 자식 노드는 2m+1번이고, 오른쪽 자식 노드는 2m+2번이다.

 

 

힙의 장점

삽입/삭제 연산이 BST보다 빠르다.

시간 복잡도는 O(log n)으로 동일하지만 힙은 무조건 완전이진트리이므로 모든 삭제/삽입 연산이 배열의 가장 끝에서 발생한다.

 

 

heapq 모듈 사용

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

 

min heap을 사용하면

원소들이 항상 정렬된 상태로 추가되고 삭제되며,

min heap에서 가장 작은 값 즉 이진 트리의 루트는 언제나 index 0에 위치한다. 

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

 

모듈 임포트 및 최소 힙 생성

import heapq

heap = []

 

원소 추가

haeapq.heappush(heap, 3)
haeapq.heappush(heap, 1)
haeapq.heappush(heap, 10)
haeapq.heappush(heap, 2)
haeapq.heappush(heap, 8)
print(heap)

[1, 2, 3, 8, 10]

시간복잡도 O(logN)

 

원소 삭제

print(heapq.heappop(heap))
print(heap)

1
[2, 3, 8, 10]

시간복잡도 O(logN)

 

삭제하지 않고 얻기

print(heap[0])

2

인덱스로 접근 가능하다.