우선순위 큐 (PriorityQueue)

PriorityQueue란?

 

스택과 큐에 대해서는 대부분 잘 알고 있을 것이다. 스택은 후입선출로 나중에 들어간 것이 먼저 나오고, 큐는 선입선출 먼저 들어간 것이 먼저 나온다. 큐이긴 하지만 기존의 큐와는 다른 특징을 가진 우선순위 큐라는 자료구조가 있다. 사용자가 지정한 우선순위를 기반으로 원소를 꺼낸다.

 

/**
 * Creates a {@code PriorityQueue} with the default initial
 * capacity (11) that orders its elements according to their
 * {@linkplain Comparable natural ordering}.
 */
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

 

java.util 패키지에 존재하는 PriorityQueue의 생성자의 인자로는 초기 용량, Comparator, Collection 등을 받을 수 있다. 인자를 받지 않는 형태는 기본 초기 용량 11, Comparator 자리에 null을 받아 다른 생성자를 호출한다. null이 전달되는 이유는 요소들의 자연적 순서를 따라 정렬하고자 하기 때문이다.

 

이때 말하는 자연적 순서는 Comparable 인터페이스를 구현한 클래스의 객체들이 가지는 기본적인 순서를 의미한다. 즉, PriorityQueue의 기본 생성자에 Comparable 인터페이스를 구현한 Integer 클래스의 객체들을 요소로 추가하면, 이 객체들의 compareTo 메소드 정의에 따라 숫자 크기에 따라 정렬이 된다.

 

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(1);
pq.add(2);

System.out.println(pq);
// 출력 결과 : 1, 3, 2

 

예를 들자면 위와 같이 우선순위 큐의 생성자를 정의하면 오름차순으로 정수들이 정렬된다. 어떤 순서로 넣든 상관없이 compareTo 메소드 정의대로 정렬이 된다.

 

사용자 정의 PriorityQueue

 

Comparator을 인자로 받기 때문에 사용자 정의대로 정렬도 가능하다. 나이가 어린 순서대로 이름을 정렬하는 Comparator 인터페이스를 구현해보자.

 

class Person {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

 

Person 객체는 이름과 나이로 이루어져 있다.

 

import java.util.*;

public class CustomPriorityQueue {

    public static void main(String[] args) {
        Comparator<Person> ageComparator = new Comparator<>() {
            public int compare(Person p1, Person p2) {
                return Integer.compare(p1.getAge(), p2.getAge());
            }
        };

        PriorityQueue<Person> pq = new PriorityQueue<>(ageComparator);

        pq.add(new Person("찰리", 25));
        pq.add(new Person("잭", 30));
        pq.add(new Person("루이스", 20));
        pq.add(new Person("샘", 35));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll().getName());
            // 출력 결과 : 루이스, 찰리, 잭, 샘
        }
    }
}

 

ageComparator는 Integer.compare() 결과를 반환한다. 우선순위 큐의 생성자에 Comparator를 넣어주면 해당 조건에 맞춰 원소들이 정렬된다. 위와 같이 4개의 요소를 추가하고 큐에 남은 원소가 없을 때까지 poll(큐 맨 앞에 있는 값 반환) 메소드로 꺼낸다. 결과를 보면 Comparator를 정의한대로 출력이 되었다.