파이썬 힙(heapq) 모듈

힙(heap)이란?

- 부모 노드가 자식 노드보다 키값이 항상 큰 '최대 힙' 과 항상 값이 작은 '최소 힙'이 있다.

- 최대값, 최소값을 빠르게 찾아내기 위한 완전이진트리 모양의 자료구조

 

 

파이썬에서 힙

-파이썬은 heapq 모듈(우선순위 큐 알고리즘) 를 제공한다.

-heapq 모듈은 최소 힙 형태로만 구현되기 때문에 최대힙의 경우 따로 구현해야한다.

 

cf. 최대힙 구현하기

import heapq
list_a=[4,1,8,9,2,5]
max_heap=[]
for i in list_a:
    heapq.heappush(max_heap,(-i,i))
while max_heap:
    print(heapq.heappop(max_heap)[1])
#9
#8
#5
#4
#2
#1

 

힙 원소 추가

heapq.heappush(heap, item)

기존 힙(heap)에 원소(item)을 추가한다. 추가와 동시에 자동으로 정렬된다.

 

힙 원소 삭제

heapq.heappop(heap)

힙에서 가장 작은 원소를 pop한 뒤 반환한다. 만약 힙이 비어 있다면 IndexError를 발생하기 때문에 주의해야 한다.

힙은 완전이진트리 구조를 가지고 있기때문에 heapq.heappop(heap) 한 값과 heap[0]의 값은 다를 수 있다.

 

힙 원소 추가 후 삭제

heapq.heappushpop(heap, item)

원수 추가 후 가장 작은 값을 삭제한다. heappush 하고 heappop를 따로 호출하는 것 보다 효율적이다.

 

리스트를 힙 형태로 만들기

heapq.heapify(x)

리스트 x를 최소힙 형태로 변환 한다. 시간 복잡도는 O(N) 이다.

import heapq
heap=[]
heapq.heappush(heap,5)
heapq.heappush(heap,1)
heapq.heappush(heap,8)
heapq.heappush(heap,4)
print(heap)
>>>[1, 4, 8, 5]
heapq.heappop(heap)
print(heap)
>>>[4, 5, 8]
list_a=[4,3,7,1]
heapq.heapify(list_a)
print(list_a)
>>>[1, 3, 7, 4]