[파이썬 힙] Heapq 사용법

heapq

heap은 최대값이나 최소값을 뽑아내기에 최적화된 자료구조이다. 파이썬에서는 heap 구현할때, heapq라는 내장라이브러리를 사용한다.

import heapq
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print(heap) #[1, 3, 7, 4]

 

출력했을때는 순서가 뒤죽박죽 섞인것처럼 보이지만.

print(heapq.heappop(heap)) # 1
print(heap) # [3, 4, 7]

 

heapq.heappop이라는 함수로 최소값을빼낼수있다.

heapq.heapify라는 함수로 기존 리스트를 힙으로 변환하는것도 가능하다.

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)	# [1, 3, 5, 4, 8, 7]

 

heapq 라이브러르는 우선순위 큐를 구현하는데에도 사용할수있다.

아래와 같이 원소가 두개인 튜플이나 리스트를 heapq.heappush를하면, 0번째 원소가 작은 것부터 빠져나온다.

import heapq

h = []
heapq.heappush(h, (3, "third"))
heapq.heappush(h, (2, "second"))
heapq.heappush(h, (4, "fourth"))
heapq.heappush(h, (1, "first"))

print(heapq.heappop(h))
print(heapq.heappop(h))
print(heapq.heappop(h))
print(heapq.heappop(h))

# (1, 'first')
# (2, 'second')
# (3, 'third')
# (4, 'fourth')