[Java] 우선순위 큐 (Priority Queue)

---

우선순위 큐 (Priority Queue)

일반적인 큐는 FIFO(First In First Out)의 구조 즉, 주문을 하기위해 줄을 서서 기다리고 가장 먼저 줄을 선 사람부터 주문을 하듯이 먼저 들어온 데이터가 먼저 나가는 구조를 가진다. Priority Queue는 들어온 순서대로 나가는 것이 아니고 데이터를 삽입 할 때 우선순위에 따라 나갈 순서를 정해주고 우선순위가 높은 데이터 먼저 나갈 수 있도록 하는 자료구조 이다.

우선순위 큐 (Priority Queue)의 특징

1. 높은 우선순위의 데이터(루트 노드)를 먼저 꺼내어 처리한다.
2. 우선순위 큐의 내부는 힙으로 구성되어 완전 이진트리의 구조로 이루어져 있다.
3. 시간복잡도는 O$(NlogN)$이다.
   
   

우선순위 큐(Priority Queue) 사용법

[ 선언 ]

import java.util.PriorityQueue;
import java.util.Collections;

// 낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 (최소 힙)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 높은 숫자가 우선 순위인 int 형 우선순위 큐 선언 (최대 힙)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 알파벳 순으로 우선 순위를 정하는 String형 우선순위 큐 선언
PriorityQueue<String> heap = new PriorityQueue<>();

// 알파벳 역순으로 우선 순위를 정하는 String형 우선순위 큐 선언
PriorityQueue<String> heap = new PriorityQueue<>(Collections.reverseOrder());

자바에서 우선순위 큐(PriorityQueue)를 사용하려면 java.util에 있는 PriorityQueue를 import 해야한다.

[ 삽입 ]

minHeap.add(1);     // 값 1 추가
minHeap.add(2);     // 값 2 추가
minHeap.offer(3);   // 값 3 추가

삽입의 경우는 add(value) 와 offer(value) 두가지의 메소드를 가진다.

add()의 경우 삽입에 성공한다면 true를 반환하고, 큐에 여유공간이 없어 삽입에 실패하면 IllegalStateException 예외를 발생시키고,
offer()의 경우 삽입에 성공한다면 true를 반환하고, 삽입에 실패한다면 false를 반환한다.

[ 삭제 ]

minHeap.remove();     // priorityQueue에 첫번째 값 제거
minHeap.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
minHeap.clear();      // priorityQueue의 모든 데이터 삭제

삭제의 경우 remove()와 poll() 두가지의 메소드로 삭제가 가능하다. 두 메소드는 공통적으로 삭제 시 루트 노드의 값을 반환한다.
remove()의 경우 우선순위 큐가 비어있을 때 삭제를 하면 IllegalStateException 예외를 발생시키고,
poll()의 경우는 null 을 반환한다.

[ 조회 ]

priorityQueue.peek();       // priorityQueue의 가장 우선순위가 높은 루트 노드값 참조

조회는 peek() 메소드를 사용하여 우선순위 큐의 루트 노드 값을 참조할 수 있다.