우선순위 큐 (Priority Queue)
큐나 스택과 같은 자료 구조 중 하나로, 각 원소가 우선순위를 가지고 있는 것이 특징이다. 우선순위 큐에서 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리된다. 우선순위가 같은 원소는 우선순위 큐 내 순서를 기준으로 처리된다.
우선순위 큐 == 힙 (?)
인터넷에 우선순위 큐에 대해 찾다 보면 힙과 함께 정리한 글이 많이 보이는데, 우선순위 큐가 힙이라고 할 수는 없다.
우선순위 큐는 리스트나 맵과 같은 추상적인 개념으로 힙, 배열, 연결 리스트 또는 다른 방식으로 구현할 수 있다. 다만 시간복잡도 등의 이유로 일반적으로 힙으로 많이 구현하는 것 같다.
아래는 우선순위 큐의 구현 방식에 따른 enqueue / dequeue 연산의 시간복잡도를 비교한 표이다.
| 구현 방식 | enqueue | dequeue |
| 배열 | O(1) | O(N) |
| 연결 리스트 | O(1) | O(N) |
| 정렬 배열 | O(N) | O(1) |
| 정렬 연결 리스트 | O(N) | O(1) |
| 힙 | O(logN) | O(logN) |
지원 연산
우선순위 큐는 아래와 같은 연산이 지원되어야 한다.
- 우선순위를 지정해 원소를 큐에 추가한다.
- 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 반환한다.
참고 문서
https://www.happycoders.eu/algorithms/priorityqueue-java/