[Python] heapq 사용법

Copyright ©2001-2020. Python Software Foundation

[Python] heapq 사용법

(글쓴날 : 2020.04.26)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

* Python3를 기준으로 작성되었습니다.

---

 

 

Python heapq 사용법

---

1) heapq란?

heapq란 자료구조 queue의 일종으로, queue의 내부 구조가 heap으로 이루어져 있다고 보시면 됩니다.

heapq는 일반 queue와 마찬가지로 추가(push), 삭제(pop) 등의 기능을 하지만, heap 구조를 유지하기 위해 추가(push) 및 삭제(pop) 시 O(log n)의 시간 복잡도가 걸리게 됩니다.

 

보통 우선순위 큐를 구현하기 위해 사용되며, heapq 모듈의 함수들은 Min Heap 기준으로 설계되어 있으므로 주의해야 합니다.

---

2) heapq 사용법

(1) heapq import

import heapq

---

(2) heapq 생성

(heapq는 생성해서 사용하는 것이 아니라 일반 리스트를 그대로 이용합니다!)

hq = []
print(hq)  # print결과 : []

---

(3) heapq.heappush( (리스트), (값) ) : 리스트에 Min Heap 기준으로 값 추가

heapq.heappush(hq, 3)
heapq.heappush(hq, 2)
heapq.heappush(hq, 1)
print(hq)  # print결과 : deque([1, 3, 2])

---

(4) heapq.heappop( (리스트) ) : 리스트에서 Min Heap 기준으로 값 삭제 후 반환

print(heapq.heappop(hq))  # print결과 : 1
print(heapq.heappop(hq))  # print결과 : 2
print(heapq.heappop(hq))  # print결과 : 3

---

(5) heapq.heapify( (리스트) ) : 기존 리스트를 Min Heap으로 변환

hq = [3, 5, 4, 1, 2]
heapq.heapify(hq)
print(heapq.heappop(hq))  # print결과 : 1
print(heapq.heappop(hq))  # print결과 : 2
print(heapq.heappop(hq))  # print결과 : 3
print(heapq.heappop(hq))  # print결과 : 4
print(heapq.heappop(hq))  # print결과 : 5

---

(6) Max Heap 구현하는 방법

마지막으로, Max Heap을 구현하는 방법에는 두 가지가 있습니다.

 

첫 번째 방식은, 추가 및 출력 시 값에 -를 붙이는 것입니다.

ex)

heapq.heappush(hq, -1)
heapq.heappush(hq, -2)
heapq.heappush(hq, -3)
 
print(-heapq.heappop(hq))  # print결과 : 3
print(-heapq.heappop(hq))  # print결과 : 2
print(-heapq.heappop(hq))  # print결과 : 1

 

두 번째 방식은, 튜플(tuple)을 이용하는 것입니다.

튜플의 첫 번째 요소에 음수화한 값을 넣고, 두 번째 요소에 원래 값을 넣은 뒤, heapq에 추가하여 출력 시 튜플의 두 번째 요소를 사용하는 원리입니다.

ex)

heapq.heappush(hq, (-1, 1))
heapq.heappush(hq, (-2, 2))
heapq.heappush(hq, (-3, 3))
 
print(heapq.heappop(hq)[1])  # print결과 : 3
print(heapq.heappop(hq)[1])  # print결과 : 2
print(heapq.heappop(hq)[1])  # print결과 : 1

---

 

 

---

 

 

여기까지, Python의 heapq 사용법에 대하여 알아봤습니다.

감사합니다!