우선순위큐란?

우선순위큐는 특정 우선순위에 따라 요소들을 저장하는 자료구조다. 자바에서는 java.util.PriorityQueue가 힙으로 구현되어있음을 확인할 수 있다.

First-In, First-Out 구조로 잘 알려진 큐에다 요소 순서를 우선순위에 의해 지정하는 개념을 추가한다고 볼 수 있다

우선순위큐의 개념

1. 우선순위 큐는 null을 허용하지 않는다

null은 우선순위 기준에 따라 비교할 수 없으니 어찌보면 당연한 말이다

2. 우선순위큐의 요소는 비교 가능해야 한다

Comparable 인터페이스를 구현하는 타입만 가능하다

또한, Comparator를 구현해서 요소의 순위를 결정할 수 있다.

요소를 비교해서 큐에 추가해야 한다

3. 가장 우선순위가 높은 요소들 중 하나가 우선순위큐의 head가 된다

동점인 요소들이 생기면 우선순위는 랜덤으로 지정된다

4. 우선순위큐는 thread-safe하지 않다

멀티스레드 환경에서는 PriorityBlockingQueue를 사용해야 한다

5. Java의 우선순위 큐는 기본적으로 min heap을 구현한다

Java의 java.util.PriorityQueue를 통해 사용하는 우선순위큐는 가장 작은 값이 가장 높은 우선순위를 갖는 min heap을 구현한다.

max heap을 사용하기 위해서는 다음과 같이 역순의 comparator를 도입해야 한다.

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

우선순위큐의 활용

생성자

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

위와 같이 우선순위큐를 생성하면 11개의 요소를 담을 수 있는 자료구조를 만든다

우선순위큐의 크기를 명시해서 생성할 수도 있다

PriorityQueue<E> pq = new PriorityQueue<E>(int initialCapacity);
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(15);

메서드

조회

Peek

가장 높은 우선순위의 요소를 조회한다

pq.peek();

Iteration

Iterator iterator = pq.iterator();
while (iterator.hasNext()) {
	System.out.println(iterator.next() + "\n");
}

Contains

우선순위큐가 명시된 요소를 포함하면 true를 반환한다

pq.contains(5);

데이터 추가

Add

우선순위에 따라 요소를 우선순위큐에 추가한다

pq.add(5);

시간복잡도: O(log N)

Java에서 우선순위 큐는 우선순위 힙으로 구현되어 있다

데이터를 추가할 수 없으면 예외를 발생시킨다

Offer

pq.offer(5);

데이터를 추가할 수 없을 때에도 예외를 원하지 않으면 offer를 사용하면 된다

데이터 삭제

Remove

메서드에 명시된 요소를 제거한다
요소가 여러 개 있다면 처음으로 발견되는 것을 제거한다

pq.remove(5);

명시된 요소가 우선순위큐에 존재하지 않아도 에러가 발생하지 않는다

Poll

가장 높은 우선순위의 요소를 조회하고 제거한다

pq.poll();

---

출처: https://www.geeksforgeeks.org/priority-queue-class-in-java/