우선순위 큐(Priority Queue)
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 큐이다.
데이터를 우선순위를 정해놓고 우선순위에 따라 처리하고 싶을 때 사용한다.
이 자료구조는 최단 경로 알고리즘에서 주로 사용된다.
이를 구현하기 위해서는 힙 자료구조를 사용하게 된다.
대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리를 지원하기 때문에 힙부터 시작해서 우선순위 큐를 구현할 일은 거의 없다.
이전까지 배웠던 큐/스택/우선순위 큐를 비교하면 아래와 같다.
| 자료구조 | 추출되는 데이터 |
|---|---|
| 스택 | 가장 나중에 삽입된 데이터 |
| 큐 | 가장 먼저 삽입된 데이터 |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
우선순위 큐 구현 1 - 힙 이용
우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용된다.
예를 들어 상품 데이터가 있고 상품에 대한 정보가 가치/무게로 구성되어있다고 가정해보자.
그러면 상품 데이터를 (가치, 상품)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다.
이후에 우선순위 큐에서 상품을 꺼내면 가치가 높은 물건이 먼저 나오게 된다.
(우선순위 큐가 최대 힙으로 구현되어 있을 때, 최대 힙은 pop할 시 가장 큰 값이 먼저 나오는 것을 이용한 것)
이게 가능한 이유는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫번째 원소를 기준으로 우선순위를 설정하기 때문이다.
언어마다 우선순위 큐 라이브러리가 최소 힙/최대 힙으로 구현되어 있는 것이 다르므로 언어마다 확인해서 사용해야 한다.
우선순위 큐 구현 2 - 배열 이용
배열을 이용해서 우선순위 큐의 기능을 구현하기 위해서는 삭제할 때마다 모든 원소를 확인해서 우선수위가 가장 높은 것을 찾아야 하므로 최악의 경우 O(N)의 시간이 소요된다.
배열 이외에도 연결리스트를 이용한 방법 또한 있으나, 시간복잡도는 배열과 비슷하다.
두 방식의 비교
아래 표는 데이터의 개수가 N개일 때, 리스트와 힙으로 구현한 우선순위 큐의 삽입/삭제 시간 비교이다.
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙 | O(logN) | O(logN) |
데이터의 개수가 N개일 때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤 다시 모든 데이터를 꺼낸다고 해보자면 시간복잡도는 NlogN(삽입) + NlogN(삭제) 이므로 O(NlogN)이 될 것이다.
이 작업은 사실 힙 정렬의 원리와 같다.
위의 작업을 리스트로 수행하려고 하면 시간복잡도는 O(N^2)이 된다.
그러므로 힙을 사용하는 것이 일반적으로 더 빠르고, N이 커질수록 리스트의 속도는 훨씬 느려지게 될 것이다.
결과적으로 위와 같은 이유로 우선순위 큐를 구현하는 데 보통 힙을 사용하게 된다.
파이썬에서의 우선순위 큐
파이썬에서는 우선순위 큐가 필요할 때 PriorityQueue 혹은 heapq를 이용할 수 있다.
일반적으로는 더 빠르게 동작하는 heapq 라이브러리를 사용한다.
우선순위 큐의 메소드
힙에서 사용하는 메소드를 그대로 사용하게 됩니다.
- heapq의 heappush으로 우선순위 큐에 값을 추가
- heapq의 heappop으로 우선순위 큐에서 값을 삭제
- peek() or top() 등으로 우선순위 큐에서 최대/최소 우선순위 값을 반환받는 것
파이썬은 heapq의 첫번째 인자인 배열의 0번째 index를 가져오면 된다.
코드에서 우선순위 큐 이용
python에서는 heapq라이브러리가 최소 힙을 지원하므로, 우선순위에 거리를 넣어서 시작 노드로부터 '거리'가 짧은 노드 순서대로 큐에서 나올 수 있도록 하여 '다익스트라 알고리즘'을 사용한다고 한다.
import heapq
pq = []
# 우선순위 큐에 (거리, 노드번호) 상태로 삽입하면 거리순으로 정렬되어 큐에 쌓일 것이다.
heapq.heappush(pq, (0, 1))
# root 노드인 1번 노드와 가장 가까운(거리가 가장 짧은) 노드를 선택하기 위해서는
# 우선순위 큐에서 그냥 노드를 pop 한 번 하면 된다.
# 큐에서 pop을 하고 그 pop한 노드를 처리한 적이 있다면 무시하고, 처리하지 않은 노드면
# 처리해주면 된다.
heapq.heappop(pq)
# 이후 1번 노드와 연결관계에 있는 것들을 거리와 함께 다시 큐에 넣어주고 ... 이런식으로 반복한다.관련문제는..
우선순위 큐 관련 문제는 최단경로를 구하는 문제를 풀어봐야 해서
관련된 개념을 공부하고나서 풀어볼 예정
출처
