[Java] PriorityQueue(우선순위 큐)란?

 

PriorityQueue(우선순위 큐)

 

일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로
스택과는 다르게 FIFO(First In First Out)의 구조, 즉 먼저 들어온 데이터가 먼저 나가는 구조를 가진다.
PriorityQueue는 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 결정하고,
그 우선순위가 높은 요소가 먼저 나가는 자료 구조이다.

 

PriorityQueue의 특징

1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.(큐에 들어가는 원소는 비교가 가능한 기준이 있어야 함)
2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
3. 내부 구조가 힙으로 구성되어 있기에 시간 복잡도는 O(nlogN)이다.
4. 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰인다.

 

사용예제

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

// 추가
priorityQueue.add(1);
priorityQueue.offer(3);

// 삭제
priorityQueue.poll(); // 첫번째 값을 반환하고 제거, 비어있다면 null
priorityQueue.remove(); // 첫번째 값 제거
priorityQueue.clear(); // 초기화

// 출력
priorityQueue.peek();