[자바] 우선순위 큐 사용하기

우선순위 큐란, 일반 큐 (First In First Out)의 구조와는 다르게, 들어간 순서와는 무관하게 자동으로 우선순위 순서대로 배열되는 자료구조 형태이다. 오름차순 또는 내림차순으로 정리될 수 있으며, 자바에서는 기본적으로 오름차순으로 설정된다. poll (큐에서의 pull)를 하면 숫자가 작은 순서대로 나오는 것이다.

 

기본 선언

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();

이렇게 선언하면 기본적으로, 오름차순으로 배열된다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

내림차순으로 배열되도록 선언하고 싶다면 이렇게 해주면 된다.

 

다음으로는 Priority Queue의 기본적인 메소드들이다.

나는 백준 1715번 문제를 풀면서 사용한 코드를 기반으로 정리해 보겠다.

for(int i = 0; i < N - 1; i++) {
            sum = 0;
            sum += pq.poll();
            sum += pq.poll();
            pq.offer(sum);
            ans += sum;
}

기본적으로, pq.poll() 함수가 우선순위 큐에 가장 앞에 있는 값(가장 작은 값)을 반환하며 제거하는 함수이다.

pq.offer(값) 함수가 우선순위 큐에 해당 값을 넣는 함수이다. 자동으로 오름차순으로 배열된다.

add(값)	큐에 해당 값 추가 값이 큐의 규칙에 따라 적절한 위치에 삽입 값 추가 성공 시 true 반환, 큐 용량 초과 시 예외를 throw한다.
offer(값)	큐에 지정된 값을 추가 값이 큐의 규칙에 따라 적절한 위치에 삽입됨 add 메소드와 유사하지만 큐가 용량을 초과해도 예외를 던지지 않고 false를 반환할 수 있다.
poll()	큐의 헤드(가장 앞에 있는 값)을 제거 및 반환 큐가 비어있다면 null을 반환 큐의 우선순위에 따라 가장 높은 우선순위를 가진 요소 제거
remove()	큐의 헤드(가장 앞에 있는 값) 제거 큐가 비어있다면 예외 throw
peek()	큐의 헤드(가장 앞에 있는 값) 반환 큐가 비어 있으면 null 반환 해당 메소드는 큐에서 요소를 제거하지 않음
element()	큐의 헤드(가장 앞에 있는 값) 반환 큐가 비어 있으면 예외 throw
isEmpty()	큐가 비어 있는 지 여부 확인 비어있으면 true, 그렇지 않으면 false를 반환
size()	큐에 있는 요소의 개수 반환
clear()	큐의 모든 요소 제거
contains(Object o)	큐에 특정 요소가 포함되어 있는 지 확인 포함되어 있다면 true, 그렇지 않으면 false 반환

 

*지피티

이 외에도 PriorityQueue 클래스는 큐의 요소들을 배열로 변환하거나, 반복자(iterator)를 통해 큐의 요소들을 순회할 수 있는 메소드도 제공합니다. PriorityQueue는 기본적으로 자연 순서(즉, 요소의 Comparable 인터페이스 구현에 따른 순서)로 요소를 정렬하지만, 생성자에서 Comparator를 제공하여 사용자 정의 순서를 사용할 수도 있습니다.