[Java] PriorityQueue(우선순위 큐) 설명과 사용법

Priority Queue(우선순위 큐)란?

 

우리가 자바에서 사용하는 큐는 FIFO 형식으로 가장 먼저 쌓인 데이터부터 추출할수 있는것으로 알고 있다.

하지만 Priority Queue는 데이터가 들어온 순서대로 나가는것이 아닌 우선순위를 먼저 결정하고 

그 우선순위가 높은 요소들부터 나가는 구조이다.

우선순위 큐는 Heap을 사용해서 구현을 한다. 그래서 값은 완전이진트리 형태로 값이저장되고

값을 추출하게 된다.

 

 

Heap과 완전 이진트리에 대한 설명은 아래 링크를 참조해보면 된다. 

https://wpioneer.tistory.com/94?category=1023663 

 

그럼 Priority Queue 의 특징을 살펴보자.

 

Priority Queue 특징

 

1. 높은 우선순위 요소를 먼저 꺼내서 처리하는 구조

(큐에 들어가는 값은 비교 가능한 기준이 있어야 한다. 예 : 숫자와 문자)

 

2. 내부 요소는 Heap으로 구성되어 있어 완전 이진트리 형태로 구성되어 있음

3. Heap 방식이기 때문에 시간 복잡도는 O(log n) 이다.

4. 우선순위를 중요시 여기거나 최소값, 최대값 을 빠르게 구할때 주로 쓰인다.

 

Priority Queue 선언 방법

 

Priority Queue를 사용하려면 

import java.util.PriorityQueue;

위의 내용을 import 하면 된다. 귀찮다면 java.util.*; 을 하면 된다.

 

그리고 이제 Priority Queue를 선언하는 방법에는 크게 4가지가 있다.

 

1. 우선순위가 낮은 숫자 순(최소 Heap)

 

선언 방법

PriorityQueue<Integer> pq = new PriorityQueue<>();

들어가는 방식은 아래의 배열의 값들을 PriorityQueue에 넣고 출력하면

int[] arr = {1,5,3,4,6,2};

[1, 4, 2, 5, 6, 3]

 

이렇게 출력이 된다. 이를 이진트리로 확인해보면 아래와 같다.

 

 

2. 우선순위가 높은 숫자순(최대 Heap)

 

선언 방법

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

아래 배열을 위의 PriorityQueue에 넣고 출력하면 아래와 같이 된다.

int[] arr = {1,5,3,4,6,2};

[6, 5, 3, 1, 4, 2]

 

이걸 이진트리로 표현하면 아래와 같다.

 

 

3. String 형 우선 순위가 낮은순 (최소 Heap)

 

선언 방법

PriorityQueue<String> pq = new PriorityQueue<>();

위 소스는 사실 숫자로 했을때와 같다. 다만 제네릭<> 안에다가 String 을 넣은 형태다.

그래도 위처럼 String에서는 어떻게 정렬이 되는지 확인해보자.

 

아래의 배열

String[] arr = {"a","d","b","f","c","w"};

[a, c, b, f, d, w]

이렇게 바뀌어서 들어가게 된다.

 

4. String 형 우선 순위가 높은순 (최대 Heap)

 

선언 방법

PriorityQueue<String> pq = new PriorityQueue<>(Collections.reverseOrder());

 

아래의 배열이 

String[] arr = {"a","d","b","f","c","w"};

[w, d, f, a, c, b]

이렇게 변환되어 저장된다.

 

 

 

PriorityQueue에 값을 저장하는 방식은 일반 Queue에 저장하는 방식과 비슷하다.

 

해당 방식은 아래링크에 넣어놨으니 확인해보면 될것 같다.

 

https://wpioneer.tistory.com/89?category=1023662