[Java] PriorityQueue(우선순위 큐) 사용법 및 예제

Priority Queue(우선순위 큐)

일반적으로 '큐(Queue)'라는 자료구조는 먼저 들어온 순서대로 데이터가 소비된다. 즉 FIFO(First In First Out)의 동작을 갖는다. 큐와 비슷한 '우선순위 큐(Priority Queue)'라는 자료구조는 들어온 순서가 아닌 저장되어 있는 데이터 중 우선순위가 높은 순서대로 데이터가 소비된다.

'Priority Queue(우선순위 큐)'는 일반적으로 힙(Heap)이라는 자료구조를 이용해서 구현한다. 입력받은 데이터를 이용해서 최대힙 혹은 최소힙을 구성하고 데이터를 꺼낼때 루트노드에서 꺼낸다. 꺼내진 루트 노드에는 힙의 마지막 노드가 삽입되어 아래로 내려가면서 자기 자리를 찾아간다.

Priority Queue는 내부적으로 힙을 이용해서 정렬된 상태를 유지하기 때문에 삽입과 삭제 연산에서 O(n*logn) 시간 복잡도를 갖는다.

Priority Queue 사용법

Priority Queue 선언

priority queue는 java.util.PriorityQueue 클래스로 구현되어 있다.

// 우선순위가 낮은 순으로 정렬
PriorityQueue<Integer> pQueue = new PriorityQueue<>();

// 우선순위가 높은 순으로 정렬
PriorityQueue<Integer> pQueue = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue 객체는 다른 컬렉션 객체와 마찬가지로 다루고자하는 데이터의 타입을 지네릭(Generic)으로 명시해줘야한다. 이 때 사용하는 클래스는 우선순위를 비교할 수 있는 Comparable 인터페이스를 구현한 클래스여야한다. 그렇지 않으면 ClassCastException을 보게 될 것이다.

생성자에 아무런 인자를 주지 않은 경우 우선순위가 낮은 순으로 데이터가 꺼내지게 된다. 높은 순으로 데이터를 꺼내기 위해서는 Collections.reverseOrder()를 생산자의 인자로 주면 된다. 정확히는 Comparator 클래스를 구현해서 생성자의 인자로 넘겨주면 된다. Collections.reverseOrder()는 Comparable 인터페이스를 구현한 클래스의 비교 연산을 뒤집은 것이다.

Comparable 인터페이스와 Comparator를 잘 구현해주면 여러가지 조건으로 우선순위를 결정할 수 있다. 나머지는 응용에 맡기겠다.

Priority Queue 값 추가

add() 메소드 혹은 offer() 메소드를 이용해서 Priority Queue에 값을 추가할 수 있다. 두 메소드는 동일하다.

pQueue.add(1);
pQueue.add(10);
pQueue.offer(5);

add() 메소드는 Priority Queue에 값을 추가한다. 힙에 값을 추가하면서 정렬된 상태를 만들어 둔다. 값에 대한 추가 연산이 성공하면 true가 반환된다. 만약 Priority Queue에 여유공간이 없으면 IllegalStateException이 발생한다. 

Priority Queue 값 삭제

poll() 메소드 혹은 remove() 메소드로 값을 하나씩 제거할 수 있고, clear() 메소드로 전체 초기화를 할 수 있다.

pQueue.poll();       
pQueue.remove();    
pQueue.clear();  

Comparator에 따라서 우선순위가 가장 높은 값 혹은 우선순위가 가장 낮은 값이 제거된다. poll() 함수는 큐가 비어있을 경우 null을 리턴한다.

clear() 메소드는 모든 엘리먼트들을 날리고 우선순위 큐를 초기화 시켜준다.

Priority Queue 값 확인

우선 순위가 가장 높은 데이터를 확인만하고, 큐에서 빼고 싶지 않을 경우 peek() 메소드를 이용한다.

pQueue.peek();

우선순위가 가장 높은 값을 확인만 한다.

Priority Queue 값 순회

다른 컬렉션과 마찬가지로 Priority Queue 값을 for 문 혹은 iterator를 이용해서 순회할 수 있다.

for (int value : pQueue) {
    System.out.println(value);
}

Iterator iterator = pQueue.iterator();
while (iterator.hasNext()) {
    int value = iterator.next();
    System.out.println(value);
}