[Python] Heap (Priority Queue)

heapq 는 "우선순위 큐(Priority Queue)"를 구현하는 데 유용함.

 

• 우선순위 큐 ) 항목의 우선순위에 따라 처리되는 데이터 구조.
• 따라서 가장 작은(또는 가장 큰) 항목을 우선적으로 처리하는데 사용됨.
• ex) 작업 스케줄링, 다익스트라 알고리즘(Dijkstra's algorithm) 등.

 

import heapq

heapq.heapify(l1) # => 자동 정렬된 list(heap)가 됨. # O(n)

# 1. 삽입/추출
heapq.heappush(lst, 0) # O(log n)
= heapq.heappop(lst) # O(log n)

# 2. 삽입+추출
= heapq.heappushpop(lst, 0) # O(log n) # 삽입 후, 바로 최솟값 추출.
= heapq.heapreplace(lst, item) # O(log n) # 최솟값 추출 후, 새 항목 삽입.

# 3. n개 반환
= heapq.nlargest(k, lst) # O(n log k) # 가장 큰 n개의 항목 반환.
= heapq.nsmallest(k, lst) # O(n log k) # 가장 작은 n개의 항목 반환.