JAVA 우선순위 큐(primary queue)

우선순위 큐?

---

JAVA에는 힙(heap)을 사용한 여러가지 자료구조가 존재한다.

이 중 이번에 다뤄 볼 자료구조는 '우선순위 큐'(primary queue)이다.

일반적으로 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로, 스텍과는 다르게 FIFO(First In First Out) 형태를 지닌다
하지만 우선순위 큐는 값이 들어온 차례대로가 아닌 값이 들어올때마다 우선순위를 정하여 그 우선순위가 높은 값이 나가는 자료구조이다.

내부 요소는 이진트리 구조로 이루어져있기 때문에 값 끼리의 비교가 수월하고, 시간 복잡도는 O(nlogn)이다.

사용법

---

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

우선, 여느 자료구조와 동일하게 사용을 위해서는 import가 필수적이다.
기본적으로 우선순위가 낮은 순으로 정렬되기 때문에 최소 힙을 원한다면 () 내부에 아무것도 없어도 되지만 우선순위가 높은 숫자를 원한다면 collections.reverseOrder()를 사용하여 반대로 출력해야한다.

자료구조의 내부 작동 순서는 아래를 보면 확인 가능하다.

이런식으로 값을 비교해가며 우선순위를 수정한다.