[자료 구조] PriorityQueue 컬렉션을 이용한 자바 우선순위 큐 :: Java Priority Queue implementing by PriorityQueue Class

우리가 지난시간에 Heap을 배웠는데, 사실 Heap은 이 Priority Queue, 우선순위 큐를 위해서 고안된 자료구조라고 해도 과언이 아니다.

우선순위 큐에 대해서 지금부터 알아가보자.

우선순위 큐

우선순위 큐는 말 그대로 우선순위(Priority) 가 존재하는 큐 이다.

 

예를들어 우리가 학생들이 있을 때, 나이 순으로 학생들을 쭉 세운다면 나이가 우선순위가 되어 나이가 크거나 작은 순서로 학생들이 정렬이 될 것이다.

 

이 말을 다시 풀어서 말 한다면, 들어온 순서에 상관 없이 우선순위가 높은 데이터가 먼저 출력된다는 뜻이다.

스택 VS 큐 VS 우선순위 큐

자료 구조	삭제 대상
스택	가장 나중에 들어온 데이터
큐	가장 먼저 들어온 데이터
우선순위 큐	가장 우선순위가 높은 데이터

여기서 신기한 사실은 우선순위 큐로 스택이나 큐를 구현할 수 있다는 것이다.

 

위의 표를 보면 알겠지만 스택과 큐는 우선순위 큐의 입장에서 본다면, 우선순위가 들어온 순서이다.

 

이를 이용하면 우선순위 큐로 스택과 큐 자료구조 모두를 구현할 수 있다.

우선순위 큐 연산의 내부 동작 과정

우선순위 큐는 내부적으로 삭제와 삽입의 연산이 이루어질 때 어떤 자료 구조로 구현이 될까?

우선순위 큐는 우리가 바로 전에 배웠던 Heap(힙 자료구조) 에 내부적인 동작에 의해 동작한다. 다른 자료형과 비교해보자.

 

Unsorted Array

정렬되지 않은 배열은 삽입이 간단하다. 그냥 기존 요소 마지막에 붙히면 되는데 이는 시간 복잡도가 O(1)이다. 하지만 삭제할 때 우선순위를 따져야 하므로 결국 배열 모든 원소를 한 번씩 확인해야 하므로 시간 복잡도는 O(n)이 된다.

Sorted Array

정렬된 배열의 삽입은 조금 복잡해진다. 삽입할 요소에 대한 우선순위를 다른 값들과 비교해야 하므로 시간 복잡도는 O(n)가 된다. 삭제가 된 뒤에도 각 요소를 앞으로 당겨줘야 한다는 점이 넘어있지만 이미 시간복잡도가 오바니까 넘어가자

Sorted, Unsorted LinkedList

정렬되지 않은 리스트나 정렬된 리스트나 사실 거기서 거기다. 배열은 연속적인 데이터의 묶음이고 리스트는 비연속적엔 노드의 연결에 의해 이루어져있는데, 삽입과 삭제 역시 우선순위를 비교해야 하므로 각각 O(n), O(1)의 시간 복잡도가 소모된다.

Heap

힙은 반정렬 상태를 유지하므로 트리의 높이에 따라 시간 복잡도가 계산되므로 O(log2N)이라는 어마어마한 시간복잡도의 단축이 존재한다.

자바의 PriorityQueue class

이제 내부 동작은 Heap에 의해 이루어 진다는 것을 알게 되었다.

 

그럼 실전에서 사용하기 위해서 자바의 PriorityQueue 클래스를 배워보자.

java.util 클래스로 컬렉션이 있는 패키지와 동일한 패키지에 존재한다.

일단 우선순위 큐를 이용하기 위해서는 가중치, 즉 우선순위가 존재해야 한다.

사람이라는 클래스를 만들어서 사람의 나이순 대로 이름을 출력시켜보자.

나이순대로 이름을 출력하기 위해서는 또 comparable 인터페이스를 이용해서 compareTo 메서드를 재정의 해아한다.

 

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

        Person p1 = new Person(10, "jang");
        Person p2 = new Person(11, "Heo");
        Person p3 = new Person(11, "park");
        Person p4 = new Person(9, "choi");
        Person p5 = new Person(8, "seo");
        priorityQueue.offer(p1);
        priorityQueue.offer(p2);
        priorityQueue.offer(p3);
        priorityQueue.offer(p4);
        priorityQueue.offer(p5);

        System.out.println(priorityQueue.size());
        while(!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll().name);
        }
    }
    private static class Person implements Comparable<Person> {
        int age;
        String name;

        Person(int age, String name) {
            this.age = age;
            this.name = name;
        }

        @Override
        public int compareTo(Person o) {
            return o.age - this.age;
        }
    }
}

우리가 주의깊게 보아야 하는 부분은 바로 Person클래스 이다.

 

Person 클래스에 정렬 기준을 나이로 정해주면 우선순위 큐의 내부 힙에 의해서 가중치가 적용된 결과를 출력하게 된다.

그럼 우선순위의 역순은?

우선순위 역순은 두 가지 방법이 있다.

1. Comparable 메서드를 역순 재정의 하는 방법
2. Collections.reverseOrder()를 PriorityQueue의 생성자 매개변수로 넘겨주는 것.

메서드의 역순 재정의는

@Override
        public int compareTo(Person o) {
            return this.age - o.age;
        }

로 반환 값을 바꿔주면 되고

 

생성자 매개변수는 다음과 같이 해주면 된다.

PriorityQueue<Person> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());