우선순위 큐란?
기본적으로 우리가 아는 Queue는 FIFO(First In First Out)의 구조로, 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조입니다.
그러나 우선순위 큐는 FIFO가 아닌, 내부에서 우선순위를 결정하고 우선순위를 높게 갖는 데이터가 먼저 나가는 자료구조입니다.
우선순위 큐는 힙, 링크드 리스트등과 같은 여러 자료구조로 구현할 수 있으나, 일반적으로는 힙으로 구현합니다.
데이터를 삽입할 때 최대힙 또는 최소힙을 구성하기에 우리가 원하는 우선순위로 데이터를 가져올 수 있습니다.
데이터를 가져올때는 루트노드를 얻고, 해당 루트노드가 삭제(poll, remove) 될 때는 루트노드가 삭제된 자리에 맨 마지막 노드를 삽입하고 아래로 내려가면서 적절한 자리를 찾아서 옮깁니다.
내부구조가 힙으로 구성되어 있기에, 해당 자료구조를 사용하는데 필요한 시간복잡도는 O(NlogN) 입니다.
우선순위 큐 사용법
선언
// import
import java.util.PriorityQueue;
// 선언
// 낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());만약 따로 우선순위 옵션을 주고 싶다면 Compartor을 통해서 구현하면 됩니다.
삽입
// 값 추가
priorityQueue.add(1);
priorityQueue.offer(2);add와 offer 모두 큐에 값을 더하는 메서드이지만,
add는 만약 삽입에 성공하면 true를 반환하고, 실패한다면 IllegalStateException를 반환합니다.
우선순위 큐에 값을 삽입하면, 그와 동시에 내부 힙을 통해서 부모와 자식간의 값을 비교해서 우선순위가 높은 순으로 정렬을 합니다.
삭제
// 큐에서 우선순위에 따라 정렬된 값중 가장 첫번째 값을 반환함과 동시에 큐에서 제거한다.
// 만약 큐가 비어있다면 null을 반환한다.
priorityQueue.poll();
// 큐에서 가장 첫번째 값을 제거한다.
priorityQueue.remove();
// 큐를 비운다.
priorityQueue.clear();우선순위 큐에서 poll()이나 remove()를 통해서 값을 제거하면 가장 우선순위가 높은 값이 제거가 됩니다.
위에서 말했듯, 제거가 되면 맨 마지막 노드의 값을 제거된 루트노드에 넣고, 힙의 성질을 이용해서 비교하여 다시 한 번 정렬합니다.
출력
priorityQueue.peek();큐에서 가장 우선순위가 높은 값을 출력하고 싶다면, peek() 메서드를 사용하면 됩니다.
poll()과는 다르게 큐에서 제거하지는 않고 그냥 어떤 값인지 알 수 있습니다.
