PriorityQueue 란?

Queue 에 관해서는 이전 포스팅에서 몇번 다룬적이 있다.

자세한 내용은 아래 참고 포스팅 참고 바란다.

 

이번 포스팅에서는 우선순위 큐 라고 하는 PriorityQueue 에 대해서 작성해볼 것이다.

 

일단 우선 순위 큐 란.

큐와 동일하게 순서대로 들어는 오되

순서대로 나가는것이 아닌, 그 안에서 우선순위를 정하고 그 순서에 맞게 out 이 되는 queue이다.

 

자세한 내부적인 절차는,

우선순위 큐는 힙을 이용하여 구현이 된다.

데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행이 된다.

 

특징들은 아래와 같다.

우선순위를 처리해야하기에 비교 가능한 기준이 있어야하고,

시간 복잡도는 힙으로 구성 되었기에 O(NLogN) 이다.

 

사용법

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

 

그리고 Queue에 값 삽입은 add와 offer등으로 일반 queue 사용과 동일하다.

제거 역시 poll , remove, clear 로 동일하다.

자세한 내용은 아래 큐 사용법을 확인바란다.

 

그리고 가장 최상단 값 역시 peek 로 사용 가능하다.

---

참고 포스팅

https://thenicesj.tistory.com/637

Queue (LinkedList) 사용법

https://thenicesj.tistory.com/314

스택(Stack), 큐(Queue), 힙(Heap) 에 대해서