[Data Structure] 우선순위 큐(Priority Queue)란?

1. 우선순위 큐(Priority Queue)의 개념

Priority Queue

우선순위 큐(Priority Queue)는 큐(Queue)와 구조가 비슷하다.

다만 다른 점이 있다면 큐(Priority Queue)는 들어온 순서대로 데이터가 나가는 것이 아니라, 우선순위를 정해 우선순위가 높은 순서대로 데이터가 나가게 된다. 우선순위 큐(Priority Queue)는 리스트(List) 또는 힙(Heap)을 이용해 구현이 가능하며 일반적으로 힙(Heap)을 많이 이용한다.

 

힙(Heap)이란?

이진 트리 자료구조의 일종으로 항상 루트 노드를 제거한다.

 

1) 최소 힙(min Heap)
- 루트 노드가 가장 작은 값을 가진다.
- 즉, 값이 작은 데이터가 우선적으로 제거된다.

2) 최대 힙(max Heap)
- 루트 노트가 가장 큰 값을 가진다.
- 즉, 값이 큰 데이터가 우선적으로 제거된다. 

데이터를 추가할 때, 우선순위를 기준으로 최소 힙(min Heap) 또는 최대 힙(max Heap)을 구성하고 데이터를 꺼낼 때, 루트 노드를 얻어낸 뒤에 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후에 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행된다.

 

우선순위 큐(Priority Queue)는 항상 정해진 우선 순위에 맞게 정렬된 상태에서 데이터를 추가하거나 빼기 때문에 우선순위를 중시하는 문제에서 유용하게 사용될 수 있다.

또한 내부 구조가 힙 구조이기 때문에 O(NlogN)의 시간 복잡도를 가진다.

 

2. 자바(JAVA) 라이브러리 우선순위 큐(Priority Queue)관련 메서드

우선순위 큐(Priority Queue) 관련 메서드는 큐(Queue)와 동일하며 하기의 큐(Queue) 게시글에 정리해 두었다.

 

[Data Structure] 큐(Queue)란?

 

3. 우선순위 큐(Priority Queue) 구현

3 - 1. 우선순위 큐(Priority Queue) 선언

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());

 

3 - 2. 우선순위 큐(Priority Queue) 데이터 추가

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

Heap Data Add

3 - 3. 우선순위 큐(Priority Queue) 데이터 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

Heap Data Remove

 

3 - 4. 우선순위 큐(Priority Queue) 데이터 조회

//int형 priorityQueue 선언(우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(2);     // priorityQueue에 값 2 추가
priorityQueue.offer(1);     // priorityQueue에 값 1 추가
priorityQueue.offer(3);     // priorityQueue에 값 3 추가
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1

4. 우선순위 큐(Priority Queue) 사용 사례

- 네트워크 트래픽 제어

- 운영체제에서 작업 스케쥴링

- 시뮬레이션 시스템

 

5. 참고(Reference)

 출처 : [Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리[코딩팩토리]