우선순위 큐?
- 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO(First-In First-Out) 구조.
- 먼저 들어온 순서대로 데이터가 나가지 않고 우선 순위를 먼저 결정하고 그 우선순위가 높은 요소들이 먼저 나가는 자료 구조.
- 힙을 이용하여 구현하는 것이 일반적
- 데이터 삽입 시, 우선순위 기준으로 최대 힙, 최소 힙을 구성하고 데이터 꺼낼 때, 루트 노드를 얻어낸 뒤 루트 노드 삭제 시, 빈 루트 노드 위치에 맨 마지막 노드를 삽입하여 아래로 내려가면서 적절한 자리로 옮기는 방식으로 구성된다.
특징
- 높은 우선순위 요소를 먼저 꺼내서 처리하는 구조. (큐에 있는 원소들을 비교할 수 있는 기준이 있어야한다.)
- 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
- 내부 구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)
- 응급실 처럼 우선순위가 중요한 상황에 쓰인다.
사용
//1. int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//2. int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
//3. String형 priorityQueue 선언 (우선순위가 낮은 문자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>();
//4. String형 priorityQueue 선언 (우선순위가 높은 문자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());import java.util.PriorityQueue 를 하고 시작.
Queue queue = new Queue<>(); 형태로 선언.
1번의 경우, 기본으로 낮은 숫자부터 1, 2, 3, 4...순서로 우선순위가 부여된다.
2번의 경우, 1번을 반대로 하는 것으로 높은 숫자를 우선순위로 4, 3, 2 , 1..부여된다.
2번과 같은 경우, Collections.reverseOrder()가 필수이다.
Priority Queue 값 추가
가장 이해가 쉬운 그림이 있어서 가져왔다.
Priority Queue 값 삭제
📄 Reference
developer