힙(Heap) 응용방법

Goal

1. 힙의 응용 방법 알아보기

 

함수 heappop() 이용하기

중요한 점은 heapq.heappop(heap)은 항상 heap에서 가장 작은 값을 반환한다는 것이다.

 

작은 수 ➡️ 큰 수

아래와 같이 1에서 5까지의 숫자가 있을 때 heap을 이용하면 가장 작은 수부터 순서대로 뽑는 것은 간단하다.

import heapq

arr = [1, 2, 3, 4, 5]

heap = []
for num in arr:
    heapq.heappush(heap, num)

for i in range(len(heap)):
    print(heapq.heappop(heap))	# 출력: 1 2 3 4 5

 

큰 수 ➡️ 작은 수

거꾸로 힙을 이용해서 큰 수부터 순서대로 뽑는 것도 가능하다.

import heapq

arr = [1, 2, 3, 4, 5]

heap = []
for num in arr:
    heapq.heappush(heap, -num)	# 마이너스한 숫자를 넣어준다 => [-1, -2, -3, -4, -5]

for i in range(len(heap)):
    print(-heapq.heappop(heap))	# 출력할 때도 다시 마이너스를 더해준다 => 출력: 5 4 3 2 1

마이너스 값으로 heap에 넣었기 때문에 이제 가장 작은 수는 1이 아니라 -5가 된다.

이제 heappop(heap)을 하면 가장 작은 수인 -5가 반환되고, 이 수에 다시 마이너스를 해주면 원래의 5가 됨으로 큰 수부터 뽑을 수 있게 된다.