java - Priority Queue(우선순위 큐)

자바로 알고리즘 문제를 풀면서 정렬관련 문제를 풀 때 ArrayList를 만들고 데이터를 빼거나 넣고 넣을 때마다 정렬을 수행했었다. 하지만 이렇게 진행하다보니 시간이 매우 많이 초과되면서 이를 해결할 방법을 찾다가 '우선순위큐' 라는 것을 찾고 간단하게 정리해 보려한다.

 

 

일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 FIFO(First In First Out)의 구조인데 먼저 들어온 데이터가 먼저 나가는 구조를 가진다. PriorityQueue는 큐와 비슷하지만 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위에 따라 순서대로 나가는 자료구조이다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸다. 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행된다.

 

Priority 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());

 

 

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

 

값 추가가 성공하면 true를 반환하고 실패하면 IllegalStateException을 발생시킨다.

값을 추가하면 자동정렬된다.

 

 

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

 

 

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//int형 priorityQueue 선언
priorityQueue.offer(2);     // priorityQueue에 값 2 추가
priorityQueue.offer(1);     // priorityQueue에 값 1 추가
priorityQueue.offer(3);     // priorityQueue에 값 3 추가
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1

 

 

 

참고 

https://coding-factory.tistory.com/603

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리