우선순위 큐 Priority Queue (Heap)

• 17 : root node (max-heap)
• 삽입 / 삭제 : O(log N)

c++ : max-heap
c++은 root node에 큰 값이 들어간다.

python: min-heap

python은 root node에 작은 값이 들어간다

from queue import PriorityQueue

pq = PriorityQueue()
pq.put(6)
pq.put(10)
pq.put(-5)
pq.put(0)
pq.put(8)

while not pq.empty():
    print(pq.get())

결과와 같이 python의 root-node는 min-head이다.

시간 초과가 걱정될 경우 heapq 사용

import heapq as hq

pq = []
hq.heappush(pq,6)
hq.heappush(pq,12)
hq.heappush(pq,0)
hq.heappush(pq,-5)
hq.heappush(pq,8)

print(pq)
while pq:
    print(pq[0])
    hq.heappop(pq)