[Python] heapq: min heap & max heap

파이썬 Heap

heapq 모듈을 사용해서 최소 힙과 최대 힙을 간단하게 구현 가능.

import heapq

자주 쓰이는 메소드로는 heapify(), heappush(), heappop()가 있다.

• heapify(heap): heap 불변성을 유지하면서 heap내부 item 값들을 min heap으로 바꿔준다.

• heappush(heap, item): heap 불변성을 유지하며 item 값을 heap으로 push해 준다.

• heappop(heap): heap 불변성을 유지하면서 heap에서 가장 작은 항목을 pop하고 반환해주는 메소드이다.
  • heappop 메소드를 사용할 때, heap이 비어있으면 indexError가 발생한다.

사용법

Min heap(최소 힙)

---

import heapq

# 1️⃣ heapify()로 min heap화
h = [7,2,4,9,1,6,5,3,8]
heapq.heapify(h)
print(h)
# >>> [1, 2, 4, 3, 7, 6, 5, 9, 8]

# 2️⃣ heappush()로 힙 정렬
h = []
for i in range(1,10):
	heapq.heappush(h,i)
print(h)
# >>> [1, 2, 3, 4, 5, 6, 7, 8, 9]

# heappop() 사용법
for i in range(len(h)):
	print(heapq.heappop(h))

Max heap(최대 힙)

---

heapq에서는 최대 힙을 제공하지 않는다.

하지만, 값의 부호를 변경하는 방식으로 최대 힙을 구현할 수 있다.

import heapq

h=[]
tmpList = [7,2,4,9,1,6,5,3,8]

# ☝🏼 부호를 바꾸면서 heappush() 수행
for i in tmpList:
	heapq.heappush(h,-i)

# ✌🏼 heappop()후 부호 변경
for i in range(len(h)):
	print(-heapq.heappop(h))

Uploaded by N2T