사진 출처 : 링크
우리가 생각하는 큐는 FIFO(First In First Out)의 자료구조로 먼저 들어간 데이터가 먼저 나온다. 우선순위 큐도 큐이다. 하지만, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다. 예를 들어 설명하려 한다.
(Ex) 병원의 응급실을 생각해보자. 모든 환자분들이 빠른 치료를 받고 완치가 되면 좋겠지만, 제일 응급한 환자부터 치료를 하게 된다. 즉, 우선순위가 높은 환자부터 먼저 치료를 받게 되는 것이다.
우선순위 큐는 평범한 스택, 큐와 비슷한 축약 자료형이다.
각 원소들은 우선순위를 가지고 있다. 따라서 높은 우선순위를 가진 원소가 먼저 처리된다.
만약 같은 우선순위를 가진 원소가 있다면, 원소의 순서에 따라 처리된다.
우선순위 큐를 구현하는 방법은 3가지로 나뉘어진다. (우선순위 큐가 힙이라는 것은 오류이다. 배열, 연결리스트, 힙을 이용하여 다양하게 구현할 수 있다.)
배열 기반 우선순위 큐
연결리스트 기반 우선순위 큐
힙(Heap) 기반 우선순위 큐 (힙 자료구조 설명은 여기에)
3가지의 방법으로 구현한 우선순위 큐의 성능은 아래의 표와 같다.
구현 방법 | 데이터 삽입 | 데이터 삭제 |
---|---|---|
배열 기반 | O(N) | O(1) |
연결리스트 기반 | O(N) | O(1) |
힙 기반 | O(logN) | O(logN) |
배열 or 연결리스트 기반 우선순위 큐를 구현할 경우 간단하게 구현이 가능하다. 하지만, 배열 or 연결리스트를 이용하여 우선순위 큐를 만들게되면 단점이 있다.
O(1)
, 삽입은 O(N)
)O(1)
, 삽입은 O(N)
)이처럼 배열 or 연결리스트 기반 우선순위 큐가 데이터 삭제 과정에서는 힙 기반 우선순위 큐보다 성능이 좋다. 하지만, 데이터 삽입 과정에서의 시간복잡도가 월등하기 때문에 일반적으로 힙 기반으로 우선순위 큐를 구현한다.
Python에서는 PriorityQueue
와 heapq
모듈을 지원한다.
코딩 테스트 환경에서는 보통 heapq
가 더 빠르게 동작하므로 heapq
모듈을 통한 우선순위 큐의 사용을 권장한다. 또한, 힙 기반 우선순위 큐를 이용할때 Python에서 힙은 최소 힙(Min Heap)으로 구성되어 있다. 힙에 넣었다가 빼면 오름차순 정렬이 기본적으로 수행된다.
from queue import PriorityQueue
q = PriorityQueue()
q.put(1)
q.put(10)
q.put(100)
q.get()
>>> 1
q.get()
>>> 10
q.get()
>>> 100
import heapq
q = []
heapq.heappush(q, 1)
heapq.heappush(q, 10)
heapq.heappush(q, 100)
heapq.heappop(q)
>>> 1
heapq.heappop(q)
>>> 10
heapq.heappop(q)
>>> 100
그러면 PriorityQueue
모듈과 heapq
의 차이는 무엇일까? 어떤 것을 써야될까? 라는 생각이 들 수 있다. 먼저 PriorityQueue
는 객체, heapq
는 여러 함수들이 있는 파일이라고 한다. (정확한 정보는 아니다!)
PriorityQueue
모듈의 메소드들은 heapq
에 비해 사용빈도가 낮고 쓰기가 힘들다. 그리고 PriorityQueue
는 lock을 제공하여 thread-safe class 이고, 완벽한 정렬을 제공한다.
하지만 heapq
는 리스트를 사용하기 때문에 thread-safe class 가 아니고, 느슨한 정렬을 제공한다. 두 모듈은 이러한 차이점이 있다고 한다. 위에 말했듯이 코딩 테스트 환경에서는 더 빠른 heapq
모듈을 사용하자!