우선 순위 큐
우선순위 큐란?
큐(queue) 는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
우선순위 큐(Priority Queue)는 삽입 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다.(ex. 최댓값)
일반적으로 우선순위 큐는 힙(heap)를 이용하여 구현한다.
사실 힙이 우선순위 큐를 위해 구현된 자료구조로 우선순위 큐가 힙이고, 힙이 우선순위 큐인 몰아일체의 경지라고 할 수 있다.
그외 어떤 자료구조를 사용하여 구현할 수 있나
다양한 자료구조들을 사용해 구현할 수 있다.
배열, 연결리스트, 힙 등을 사용하여 구현 가능하다.
구현
각 구현 방식의 시간복잡도는 다음과 같다.
| 구현 방법 | enqueue() | dequeue() |
|---|---|---|
| 배열 (unsorted array) | O(1) | O(N) |
| 연결 리스트 (unsorted linked list) | O(1) | O(N) |
| 정렬된 배열 (sorted array) | O(N) | O(1) |
| 정렬된 연결 리스트 (sorted linked list) | O(N) | O(1) |
| 힙 (heap) | O(logN) | O(logN) |
사용 사례
- 알고리즘(다익스트라, 프림 등)
- CPU 작업 스케줄링
- 이벤트 처리
- 데이터 압축