[CS] 우선순위 큐 (JAVA)

우선순위 큐의 특징

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
우선순위 큐(Priority Queue)는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

우선순위 큐를 사용하기 위해서는 Comparable 인터페이스 또는 Comparator 인터페이스를 재정의해야 한다. 각각 compareTo 메소드와 compare 메소드를 재정의해야 되는데 거기서 우선순위 조건을 리턴해주면 우선순위 큐에서 알아서 우선순위대로 정렬해준다. 

 

우선순위 큐는 일반적으로 힙을 이용하여 구현한다. 데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다. 내부 요소들이 힙으로 구성되어 이진 트리 구조로 이루어져 있다. 우선순위 큐의 삽입과 삭제는 \(O(logN)\) 의 시간복잡도를 가지므로 우선순위 큐를 이용한 정렬은 \(O(NlogN)\) 의 시간 복잡도를 가진다.

 

우선순위 큐의 선언

우선순위 큐를 사용하려면 java.util.PriorityQueue를 import해야 한다.

선언을 하면 기본적으로 숫자가 낮은 순으로 우선순위가 결정되서 큐 내에서 오름차순으로 정렬된다.

내림차순으로 정렬을 하고 싶다면 Collections.reverseOrder() 메서드를 사용하면 된다.

import java.util.PriorityQueue;
import java.util.Collections;

// 낮은 숫자가 우선 순위인 우선순위 큐
PriorityQueue<Integer> pqLowest = new PriorityQueue<>();

// 높은 숫자가 우선 순위인 우선순위 큐
PriorityQueue<Integer> pqHighest = new PriorityQueue<>(Collections.reverseOrder());

 

우선순위 큐에서 데이터 추가

우선순위 큐에서 데이터를 추가하는 방법은 add()와 offer()이 있다.

둘의 차이점은 문제 상황에서 add()는 예외를 발생시키지만 offer()는 false를 리턴한다.

// add()의 경우, 값 추가 성공 시 true를 반환하고 실패 시 IllegalStateException 에러 발생
pq.add(X);

// offer()의 경우, 값 추가 성공 시 true를 반환하고 실패 시 false를 반환
pq.offer(Y);

 

우선순위 큐에서 데이터 삭제

우선순위 큐에서 데이터를 삭제하는 방법은 remove()와 poll()이 있다.

둘의 차이점은 문제 상황에서 remove()는 예외를 발생시키지만 poll()는 null을 리턴한다.

또한, clear()도 있는데 큐 안의 모든 데이터를 초기화할 수 있다.

// remove()의 경우, 성공 시 큐의 맨 앞에 있는 값 반환 후 삭제
// 큐가 비어 있을 때에는 NoSuchElementException 에러 발생
pq.remove();

// poll()의 경우, 성공 시 큐의 맨 앞에 있는 값 반환 후 삭제
// 큐가 비어 있을 때에는 null 반환
pq.poll();

// 큐 전체 비우기
pq.clear();

 

우선순위 큐에서 맨 앞 값 확인

우선순위 큐에서 맨 앞 값을 확인하는 방법은 element()와 peek()이 있다.

둘의 차이점은 문제 상황에서 remove()는 예외를 발생시키지만 poll()는 null을 리턴한다.

// element()의 경우, 성공 시 큐의 맨 앞에 있는 값 반환
// 큐가 비어 있을 때에는 NoSuchElementException 에러 발생
pq.element();

// peek()의 경우, 성공 시 큐의 맨 앞에 있는 값 반환
// 큐가 비어 있을 때에는 null 반환
pq.peek();