[Java] PriorityQueue

1. PriorityQueue?

 'PriorityQueue' 클래스는 힙 데이터 구조에 기반한 우선순위 큐이다. 해당 큐는 구성 시 지정된 순서(요소의 자연적 순서 또는 명시적 비교기에 의해 부과한 순서)에 따라 요소를 정렬한다.

 

 요소에 대한 검색 작업(poll, remove, peek 등)을 하면 큐의 헤드에 접근한다. 우선순위 큐의 헤드는 지정된 순서와 관련해 가장 작은 요소를 말한다. 만약 여러 요소가 최소 값으로 묶여있다면 큐의 헤드는 요소들 중 하나이다(즉, 묶음이 임의로 끊어진다).

 

우선순위 큐는 'null' 요소를 허용하지 않는다. 또한 자연적 순서에 의존하는 우선순위 큐의 경우 비교 불가능한 객체의 삽입도 허용하지 않는다(해당 경우 객체를 삽입하면 ClassCastException 이 발생할 수 있음).

 

 우선순위 큐에는 제한이 없지만 요소를 저장하는데 사용되는 배열의 크기를 제어하는 내부 용량을 갖는다. 항상 최소한의 큐 크기만큼 가지며, 요소가 추가되면 용량이 자동으로 늘어난다.

 

 'PriorityQueue' 클래스와 해당 'iterator' 은 'Collection' 및 'Iterator' 인터페이스의 모든 선택적 메서드를 구현한다. 'Iterator' 에서 제공하는 'iterator()' 메서드와 'Spliterator' 에서 제공하는 'spliterator()' 메서드는 특정 순서로 우선순위 큐의 요소를 순회하는 것을 보장하지 않는다. 순차적으로 순회해야 하는 경우 'Arrays.sort(pq.toArray())' 사용을 고려해야 한다.

 

 'PriorityQueue' 는 동기화를 제공하지 않는다. 스레드 중 하나라도 해당 큐를 수정하고 있을 때, 다른 (여러) 스레드가 인스턴스에 동시에 접근하면 안된다. 만약 다른 스레드로부터 안전하려면 'java.util.concurrent.PriorityBlockingQueue' 클래스를 사용해야 한다.

 

 해당 큐에 요소를 넣거나 제거하는 메서드(offer, poll, remove(), add)에 대해 'O(log(n))' 시간을 제공한다. 해당 시간은 'remove(Object)' 와 'contains(Object)' 메서드에 대한 선형시간이며, 검색 방법(peek, element, size)에 대한 일정한 시간을 말한다.

 

 'PriorityQueue' 클래스는 Java Collections Framework 의 멤버이다.

 

 

2. 선언 방법

// 기본(큐 헤드 = 우선순위가 가장 낮은 요소)
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 큐 헤드 = 우선순위가 가장 높은 요소
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

 

 

3. 메서드

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(100);
pq.add(4);
pq.offer(24);
pq.offer(55);

System.out.println("큐 요소 : " + pq);
System.out.println("큐 요소 개수 : " + pq.size());
System.out.println("-----------------");

System.out.println("첫 번째 요소 : " + pq.poll());
System.out.println("남은 큐 요소 : " + pq);

System.out.println("-----------------");
System.out.println("첫 번째 요소 : " + pq.peek());
System.out.println("남은 큐 요소 : " + pq);

System.out.println("-----------------");
System.out.println("첫 번째 요소 : " + pq.remove());
System.out.println("남은 큐 요소 : " + pq);
System.out.println("큐가 비어있는지 확인 : " + pq.isEmpty());

System.out.println("-----------------");
pq.clear();
System.out.println("남은 큐 요소 : " + pq);
System.out.println("큐가 비어있는지 확인 : " + pq.isEmpty());

// 출력 결과
큐 요소 : [4, 55, 24, 100]
큐 요소 개수 : 4
-----------------
첫 번째 요소 : 4
남은 큐 요소 : [24, 55, 100]
-----------------
첫 번째 요소 : 24
남은 큐 요소 : [24, 55, 100]
-----------------
첫 번째 요소 : 24
남은 큐 요소 : [55, 100]
큐가 비어있는지 확인 : false
-----------------
남은 큐 요소 : []
큐가 비어있는지 확인 : true

 

• add() : 큐에 요소를 추가한다. 만약 큐의 내부 용량이 가득 찰 경우 에러가 발생한다.
• offer() : 큐에 요소를 추가한다. 만약 큐의 내부 용량이 가득 찰 경우 'false' 를 반환한다.
• size() : 큐의 크기(큐에 저장된 요소의 개수)를 반환한다.
• poll() : 큐의 헤드(첫 번째 요소)를 반환하고 큐에서 제거한다. 큐가 비어있다면 null 을 반환한다.
• peek() : 큐의 헤드(첫 번째 요소)를 반환한다. 해당 요소를 큐에서 제거하지는 않는다.
• remove() : 큐의 헤드(첫 번째 요소)를 반환하고 큐에서 제거한다. 큐가 비어있다면 에러가 발생한다.
• clear() : 큐에 저장된 모든 요소를 제거한다. 즉, 비어있는 큐로 만든다.
• isEmpty() : 큐가 비어있는지 확인한다. 비어있다면 'true', 요소가 있다면 'false' 를 반환한다.

---

참고 문서

• Java Tutorials - Queue Implementations