JAVA - Priority Queue(우선순위 큐) 알아보기

개요

오늘은 코딩테스트 문제를 풀이하다가 알게된, Queue 종류중 하나인 Priority Queue 에 대해 알아보겠습니다.

먼저 Queue 는 데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로 First In First Out (FIFO)의 구조로 이루어져 있고 

이는 말 그대로 먼저 적재된 데이터가 먼저 나가게 됩니다. 그 예로 가장 적절한 건 아마 대기표일겁니다.

은행이나 식당에서 먼저 대기표를 뽑은 사람이 먼저 들어가는 방식과 동일합니다. 

 

하지만 오늘 알아볼 우선순위 큐 는 순서대로 데이터를 적재하고 관리하는게 아닌 선언할때 우선순위를 먼저 정한 후 

그 우선순위에 따라 자동 정렬되어 데이터가 나갈 때 우선순위가 높은 순서대로 추출되게 됩니다. 

 

특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조(큐에 들어가는 요소는 비교가 가능한 기준이 있어야함)
• 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어짐
• 내부구조가 힙으로 구성되어 있어 시간복잡도는 O(NLogN)
• 예로 응급실과 같이 우선순위가 중요한 상황에서 주로 쓰임

 

예제

import java.util.PriorityQueue;

// int타입 -> 우선순위가 낮은 숫자부터 
PriorityQueue<Integer> low = new PriorityQueue<>();

// int타입 -> 우선순위가 높은 숫자부터
PriorityQueue<Integer> high = new PriorityQueue<>(Collections.reverseOrder());

// String타입 -> 우선순위가 낮은 순
PriorityQueue<String> lowStr = new PriorityQueue<>();

// String타입 -> 우선순위가 높은 순
PriorityQueue<String> lowStr = new PriorityQueue<>(Collections.reverseOrder());


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

// 값삭제
high.poll();
high.remove();
high.clear();

// Queue 우선순위 중 가장 높은 값 출력
lowStr.peek(); //  2