[자료구조] 힙(heapq)

힙(heapq)이란?

 

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

 

 

최소 힙(min heap)

 

루트 노드가 가장 작은 값을 가진다. 따라서 값이 작은 데이터가 우선적으로 제거된다. 즉, 부모 노드가 항상 자식 노드보다 작다.

 

최대 힙(max heap)

 

루트 노드가 가장 큰 값을 가진다. 따라서 값이 큰 데이터가 우선적으로 제거된다. 즉, 부모 노드가 항상 자식 노드보다 크다.

파이썬에서 heapq 모듈을 사용하여 구현할 수 있다.

import heapq

q= []
a = [4,9,6,11,8]
for i in range(len(a)):
    heapq.heappush(q,a[i])
print(q)
#q = [4, 8, 6, 11, 9]

for i in range(len(a)):
    print(heapq.heappop(q)) # 4 6 8 9 11