[Java]우선순위 큐(Priority Queue) 튜토리얼

이전에 자료구조에 대해 얕게 공부하면서 큐(Queue)에 대한 글을 올린 적이 있다.

 

2022.07.25 - [Development/Java] - [Java]자료구조 - Queue

[Java]자료구조 - Queue

먼저 큐에 대해 복습하자.

 

큐는 대기줄이라는 의미를 가지고 있다.

 

위 그림처럼 데이터의 입력과 출력 방향이 따로 정해져 있으며,

 

먼저 들어간 데이터가 먼저 나오는 선입선출(FIFO - First In First Out) 구조로 이루어져 있다.

 

추가로 데이터를 한 번에 하나씩만 넣고 뺄 수 있다는 특징도 있다.

 

이번 글에선 이런 큐를 구현하고 상속받은 특별한 아이인 우선순위 큐(Priority Queue)에 대해 역시 얕게 알아본다.

 

Priority Queue

 

먼저 계층도를 보자.

 

우선순위 큐는 위 그림처럼 AbstractQueue를 상속받고 있으며, AbstractQueue는 다시 Queue를 구현하고 있다.

 

AbstractQueue는 추상 클래스로, 사실상 우선순위 큐가 두 컴포넌트를 구현하고 상속받는다고 생각해도 된다.

 

또한 이름에서 볼 수 있듯이 뭔가 우선순위(Priority)를 가진 자료구조라고 유추할 수도 있다.

 

그래서 일반 큐와 우선순위 큐는 뭐가 다른 걸까?

 

정답부터 말하면 우선순위 큐는 내부적으로 우선순위를 가진 알고리즘을 이용해 입력되는 값들을 정렬한다.

 

여기서 주로 사용되는 구현 알고리즘이 힙(Heap) 자료구조를 활용한 방법인데,

 

O(log N)의 시간복잡도를 갖는 완전 이진트리 형태의 우선순위 자료구조라고만 알고 넘어가자.

 

계속해서 우선순위 큐에 자료가 저장되는 것을 그림으로 살펴보자.

 

값이 들어오면 알아서 오름차순으로 정렬해주는 것을 확인할 수 있다.

 

즉 우선순위 큐의 기본 우선순위는 오름차순이다.

 

그림은 정수로 그렸지만 문자나 문자열도 당연히 가능하며, 제네릭이기 때문에 임의의 타입도 정렬이 가능하다.

 

위 그림을 코드로 구현하면 아래와 같다.

import java.util.PriorityQueue;

public class Practice {
    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        priorityQueue.add(10);
        priorityQueue.add(100);
        priorityQueue.add(1); // 입력 순서 상관 없음

        priorityQueue.add(17);

        System.out.println(priorityQueue.poll());
    }
}

1

추가로 오름차순이 아닌 내림차순으로 정렬하려면

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

와 같이 생성하면 되고,

 

우선순위를 커스터마이징 하고 싶으면 정렬 대상 객체로 Comparable이나 Comparator를 구현해 지정해주면 된다.