[Python] heap

heapq

import heapq

heapq 모듈을 사용한다

보통 큰거순서대로 뽑거나, 작은거 순서대로 뽑거나 뭐 그런 것들을 활용할 때 사용된다.

---

heapify

import heapq

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

print(heap)
output : [1, 4, 2, 5, 6, 7, 3, 8]

heapq.heapify(리스트) : 리스트 자체를 heap으로 바꿔버린다.
기본적으로 heap은 min heap으로 만들어진다

---

heappush

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 9)
heapq.heappush(heap, 1)
heapq.heappush(heap, 33)

print(heap)
output : [1, 9, 5, 33]

일반적인 리스트에 heappush 를 이용해서 넣으면서 heap을 만들 수도 있다.

---

heappop

import heapq

heap = [100, 1, 2, 3, 4, 5, 6, 7, 8]
heapq.heapify(heap)

while len(heap) != 0:
	n = heapq.heappop(heap)
	print(heap, n)

output
[2, 3, 5, 7, 4, 8, 6, 100] 1
[3, 4, 5, 7, 100, 8, 6] 2
[4, 6, 5, 7, 100, 8] 3
[5, 6, 8, 7, 100] 4
[6, 7, 8, 100] 5
[7, 100, 8] 6
[8, 100] 7
[100] 8
[] 100

heap으로 된 리스트를 heappop 을 이용하면 작은 것 순서대로 빼준다.
리스트가 처음에 heap이 아니면 처음건 해당 리스트의 0번째 원소를 뽑아낸다.

---

max_heap 만드는 법

기본적으로 heapq 모듈이 min heap을 만들어서
max_heap은 다른 방법으로 만들어야한다.

import heapq

arr = [9, 2, 1, 8, 100, 50]
heap = []

for n in arr:
	heapq.heappush(heap, (-n, n))

print(heap)
print()

while len(heap) != 0:
	n = heapq.heappop(heap)
	print(heap, n[1])

output
[(-100, 100), (-9, 9), (-50, 50), (-2, 2), (-8, 8), (-1, 1)]

[(-50, 50), (-9, 9), (-1, 1), (-2, 2), (-8, 8)] 100
[(-9, 9), (-8, 8), (-1, 1), (-2, 2)] 50
[(-8, 8), (-2, 2), (-1, 1)] 9
[(-2, 2), (-1, 1)] 8
[(-1, 1)] 2
[] 1

튜플로 넣어주면 튜플의 첫번째 원소 기준으로 heap정렬 된다.