[Python] 우선순위 큐와 힙(PriorityQueue & heapq)

🔍 우선순위 큐와 힙(PriorityQueue & heapq)

우선순위 큐(힙 큐) 문제들을 분명 풀었던 기억이 있는데, 그때도 얼렁뚱땅 풀었던 기억이 난다.
오늘 절댓값 힙(백준 11286번) 문제를 푸는데, 우선순위 큐는 기억이 나지 않아 deque로 풀어보니 역시나 시간초과가 났다.

이참에 우선순위 큐에 대해 정리해놓아야겠다 생각이 들어 작성해 본다.
대략적인 개념과 파이썬에서의 사용 방법을 정리해보려 한다.

공식 문서와 이것이 코딩 테스트다, 기타 블로그 등을 참고하였다.

---

📃 우선순위 큐(Priority Queue)

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
데이터를 우선순위에 따라 처리하고 싶을 때 사용함

구현 방법 2가지

1. 리스트를 이용하여 구현 (삽입: O(1), 삭제: O(N))
2. 힙(heap)을 이용하여 구현 (삽입: O(logN), 삭제: O(logN))

---

🐍 파이썬에서의 우선순위 큐

1️⃣ heapq

파이썬 heapq 모듈
완전 이진트리 기반의 최소 힙 자료구조
루트노드는 heapq에서 가장 작은 값

import heapq

heap = []

heapq.heappush(heap, item) # item 값을 heap으로 push
heapq.heappop(heap) # 가장 작은 항목을 pop, 비어 있다면 IndexError 발생 // pop하지 않고 가장 작은 항목에 접근하려면 heap[0] 사용할 것

그 외에 heappushpop, heapify 등 다양한 함수들이 있지만, 제일 많이 사용되는 push와 pop에 대해서 정리해 보았다.

최소 힙 자료구조이므로 가장 큰 값부터 pop 하고 싶다면(최대 힙 구조를 사용하고 싶다면), (-item, item)의 튜플 형태로 push 해주면 된다.

2️⃣ PriorityQueue

스택오버플로우 참고

PriorityQueue 내부를 확인해보면 heapq 그 자체를 사용하고 있다.

heapq와 PriorityQueue 차이점

1. heapq에는 heappush와 heappop, PriorityQueue에는 put, get 메서드가 존재한다.
2. 스레드의 안전을 요구하는 상황에서는 PriorityQueue, 아니라면 heapq를 사용하는 것이 좋다.
   1. heapq 속도가 더 빠르다.

따라서 코딩 테스트의 경우 PriorityQueue를 사용하는 것보단 heapq를 사용하는 것이 맞겠다.