[Java] 우선순위 큐(PriorityQueue) 사용법
우선순위 큐(PriorityQueue) 란
일반적인 큐(Queue)는 FIFO(First In First Out)를 따르는 자료 구조다. 첫번째로 넣은 값이 첫번째로 나온다. 이에 비해 우선 순위 큐는, 들어간 순서가 아닌, 우선 순위가 높은 순서대로 나온다. 우선 순위 큐는 완전 이진 트리로 구현되어있어, 내부의 시간 복잡도는 O(NlogN)이다. 우선 순위를 중요시해야 할 상황에서 사용된다. 새로운 값을 넣을 때마다 매번 우선순위를 재조정하므로, 정말 필요한 때에만 한정적으로 사용해야 한다.
우선 순위 큐의 중요 메서드
일반적인 큐에서 사용하는 메서드들을 그대로 사용할 수 있다. 알고리즘에서 자주 사용하는 ArrayDeque와 비교해보자.
add(E e)
ArrayDeque: 큐의 뒤에 요소를 추가한다.
PriorityQueue: 큐에 요소를 추가하면서 우선순위에 따라 정렬한다.
offer(E e)
ArrayDeque: 큐의 뒤에 요소를 추가하고, 성공하면 true, 실패하면 false를 반환한다.
PriorityQueue: 큐에 요소를 추가하고 내부적으로 우선순위에 따라 정렬한다.
poll()
ArrayDeque: 큐의 앞에 있는 요소를 제거하고 반환한다. 비어있을 경우 null을 반환한다.
PriorityQueue: 우선순위가 가장 높은 요소를 제거하고 반환한다. 큐가 비어 있으면 null을 반환한다.
remove()
ArrayDeque: 큐의 앞에 있는 요소를 제거하고 반환한다. 큐가 비어 있으면 예외를 던진다.
PriorityQueue: 우선순위가 가장 높은 요소를 제거하고 반환한다. 큐가 비어 있으면 예외를 던진다.
peek()
ArrayDeque: 큐의 앞에 있는 요소를 반환하되, 제거는 하지 않는다. 큐가 비어 있으면 null을 반환한다.
PriorityQueue: 우선순위가 가장 높은 요소를 반환하되, 제거는 하지 않는다. 큐가 비어 있으면 null을 반환한다.
element()
ArrayDeque: 큐의 앞에 있는 요소를 반환하되, 제거는 하지 않는다. 큐가 비어 있으면 예외를 던진다.
PriorityQueue: 우선순위가 가장 높은 요소를 반환하되, 제거하지 않는다. 큐가 비어 있으면 예외를 던진다.
clear()
ArrayDeque, PriorityQueue 둘다 초기화한다.
차이점이 있는 주요 메서드로는 addFirst, addLast, removeFirst, removeLast가 있다. 이것들은 Deque 인터페이스 안에 있기 때문에, 우선 순위 큐에는 없다. 우선 순위 큐에는 요소를 특정 위치에 추가하는 메서드가 없기 때문이다.
일반적으로 큐 자료구조는 index를 얻어오거나, index로 접근할 수가 없기 때문에, PriorityQueue에서 특정 인덱스 값을 얻어오려면, toArray 등을 사용해 다른 자료구조로 변경해야 한다는 것이 주의점이다.
Comparator의 사용
우선 순위는 Comparator를 추가해 조절할 수 있다. 다음은 내림차순으로 int형을 정렬한 예시이다.
PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
기본 자료형의 경우 Comparator는 생략 가능하다. 다음은 int형으로 우선 순위 큐를 사용하는 예시이다. 이 경우 Integer형의 기본인 오름차순으로 정렬된다.
PriorityQueue<Integer> q = new PriorityQueue<>();
Comparable의 사용
우선 순위 큐를 사용하려면, 모든 객체가 비교 가능해야 한다. 이를 위해 객체에 Comparable Interface를 구현해야 한다. 다음은 Cell이라는 클래스로 우선 순위 큐를 사용하는 예시이다.
PriorityQueue<Cell> pq = new PriorityQueue<>();
우선 순위를 주기 위해서는 일반적인 compareTo와 같은 방식을 취한다. 매개변수는 하나이고, 내부의 this와 외부 인자끼리 비교하는 방식이다.
class Cell implements Comparable<Cell> {
int r;
int c;
Cell(int r, int c) {
this.r = r;
this.c = c;
}
@Override
public int compareTo(Cell o) {
if (this.r == o.r) {
return this.c - o.c;
}
return this.r - o.r;
}
}
여기서 조심할 것은, compareTo가 5를 return한다고 해서 5만큼의 우선 순위가 가는 것이 아니라는 점이다. compareTo는 양수, 0, 음수만을 구분한다. 삼항 연산자로 할 수도 있지만, 복잡하게 compareTo를 이어 갈 경우, 구분이 어려워지므로 if 문을 사용해 구현했다. compareTo 안에서, String, Integer 의 내부에 있는 비교 메서드 compare를 사용해도 된다.
