[Python] heapq 라이브러리 사용하기

[5, 9, 7, 1, 2, 5, 6, 3]
[1, 2, 5, 3, 5, 7, 6, 9]

heapq

• binary tree 기반의 min heap을 제공함

import heapq

초기화

• 빈 list에 heapq 라이브러리를 사용하여 heap 구현

heap = []

---

확인

최솟값을 확인하고 싶을 때는 idx를 통해 접근하면 된다.

[0]은 최솟값이 들어있지만 [1]에 2번째로 최솟값이 들어있다고 볼 순 없다.(tree 구조를 가지기 때문)

heap[0]

추가

• heappush(heap, value)

heap = []

heapq.heappush(heap,1)
heapq.heappush(heap,5)
heapq.heappush(heap,9)
heapq.heappush(heap,2)

print(heap)

[1, 2, 9, 5]

---

삭제

• heappop(heap)
• 가장 작은 값 list[0]의 값을 return 하고 지워버림
• 데이터를 지우고 싶지 않다면 index로 접근하여 확인해야 함

print(heapq.heappop(heap))
print(heap[0])
print(heap)

1
2
[2, 5, 9]

---

list를 heap으로 변환

• list 반환이 아니기 때문에 원본이 필요하다면 따로 copy를 해야 한다.

a = [5,9,7,1,2,5,6,3]
print(a)
heapq.heapify(a)
print(a)

[5, 9, 7, 1, 2, 5, 6, 3]
[1, 2, 5, 3, 5, 7, 6, 9]

---

Maxheap

• heappush(heap, (priority, value))
• 우선순위가 작은 순서대로 heap 구성

b = [5,8,9,1,5,4,6]
h = list()
for i in b:
    heapq.heappush(h, (-i, i))
print(h)
while h:
    print(heapq.heappop(h)[1])

[(-9, 9), (-5, 5), (-8, 8), (-1, 1), (-5, 5), (-4, 4), (-6, 6)]
9
8
6
5
5
4
1