[python] 힙(heap)

힙 (Heap)

최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조로, 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙인 최대힙(max heap)과 각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙인 최소힙(min heap)이 있다.

여기서 키 값의 대소관계는 부모-자식 노드 사이에만 성립하며 형제노드 사이에는 영향을 미치지 않는다. 대부분 완전이진트리를 사용하며 시간복잡도는 O(logN) 이다.

heapq

파이썬에서 제공하는 내장모듈로, 일반적인 리스트를 min heap처럼 다룰 수 있게 해준다. 자바의 PriorityQueue클래스와 비슷하다.

항상 노드들이 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치한다.

# 모듈 임포트
import heapq

list = [3, 2, 7, 9, 5]

# 존재하는 리스트를 최소힙으로 변환
heapq.heapify(list)

# 노드 추가 (자동으로 정렬)
heapq.heappush(list, 1)

# 노드 삭제 (삭제는 가장 작은 원소만 가능하며, 삭제 후에는 그 다음으로 작은 원소가 루트가 됨)
heapq.heappop(list)

# 인덱스를 사용해서 접근할 수 있다
print(list[0], list[2])

주의할 점은 형제노드 사이에는 대소관계가 정해져 있지 않기 때문에 list[1]과 list[2]의 대소관계는 알 수 없다.