우선순위 큐(Priority Queue)

🔙뒤로가기

Priority Queue는 데이터를 입력받을 때마다 정렬하는 것이 아니라, 데이터를 추출할 때마다 가장 우선순위가 높은 데이터를 선택해서 추출하는 자료구조이다. 우선순위 큐는 내부적으로 힙(Heap)이라는 자료구조를 기반으로 만들어져 있다.

우선순위 큐의 특징

각 요소는 우선순위를 가짐: 우선순위 큐에서는 각 요소가 어떤 기준에 따라 우선순위를 가지고 있다. 이 우선순위는 요소를 비교할 수 있는 어떤 방법이든 될 수 있다.
우선순위가 가장 높은 요소부터 추출: 우선순위 큐에서 요소를 추출하면, 그 중 우선순위가 가장 높은 요소가 추출된다. 만약 우선순위가 같은 요소가 여러 개 있다면, 그 중 어떤 것이 추출될지는 우선순위 큐의 구현에 따라 다르다.
O(logN)의 시간 복잡도: 우선순위 큐는 힙을 기반으로 만들어져 있기 때문에, 데이터를 입력하거나 삭제할 때 로그 시간 복잡도를 가진다. 이는 큰 데이터 세트에서 효율적이다.
다양한 알고리즘에서 사용: 예를 들어, Dijkstra's algorithm, Heap Sort, Prim's algorithm 등 많은 알고리즘에서 사용.

자바에서는 java.util.PriorityQueue 클래스를 통해 우선순위 큐가 제공된다. 이 클래스는 java.util.Queue 인터페이스를 구현하며, 요소를 자연스러운 순서(자연 순서)에 따라 또는 Comparator에 의해 제공되는 순서에 따라 정렬한다.

Comparator

Java에서는 Comparator 인터페이스를 사용하여 객체들의 정렬 순서를 사용자가 직접 지정할 수 있다. 이는 Comparable 인터페이스와 다르게, 객체 자체에 정렬 순서를 포함시키지 않고 별도로 정의하여 사용하는 장점이 있다.

Comparator 인터페이스는 다음의 메서드를 포함하고 있다:

int compare(Object o1, Object o2): 두 객체의 순서를 비교한다. o1이 o2보다 작으면 음수를, 같으면 0을, 크면 양수를 반환한다.
boolean equals(Object obj): Comparator가 특정 객체와 같은지를 판별한다.

우선순위 큐에서는 **Comparator**를 사용하여 우선순위를 결정할 수 있다. Comparator 인스턴스를 우선순위 큐의 생성자에 전달하여, 그 큐가 요소를 정렬하는 방식을 지정할 수 있다.

예제 코드

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // Comparator를 정의
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // o1 < o2이면 양수를 반환하여 내림차순으로 정렬
                return (o1 < o2) ? 1 : (o1.equals(o2) ? 0 : -1);
//                                      동일한 객체을 경우 0 반
            }
        };

        // 정의한 Comparator를 사용하는 우선순위 큐를 생성
        PriorityQueue<Integer> queue = new PriorityQueue<>(comparator);

        // 큐에 요소 추가
        queue.add(3);
        queue.add(1);
        queue.add(4);
        queue.add(1);
        queue.add(5);

        // 요소를 꺼내면 내림차순으로 정렬된 순서대로 출력
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}