[JAVA] Prioirty Queue 우선순위 큐 (자료구조)

 

 

우선순위 큐란 ?

 

-  일반적인 큐의 구조 FIFO(First In First Out)의 구조를 가지지만, 데이터가 들어온 순서대로 빠져나가는 것이 아니라, 우선순위를 결정하고, 우선순위에 따라 데이터가 출력되는 구조입니다 .

 

- 내부가 힙의 구조로 되어있기 때문에 O(nlogn)의 시간복잡도를 가지게 됩니다. 

 

- 배열에 값을 추가하면서 따로 정렬하지 않더라도 자동으로 정렬되는 것이 장점입니다. 

 

 

우선순위 큐 선언

import java.util.PriorityQueue;

PriorityQueue<> hq = new PriorityQueue<>();

 

 

우선순위에 따른 최대, 최소 힙 

 

- 최소힙: 최솟값이 우선순위인 큐

import java.util.PriorityQueue;

PriorityQueue<> hq = new PriorityQueue<>();

 

- 최대힙: 최댓값이 우선순위인 큐 

import java.util.PriorityQueue;
import java.util.Collections; 

PriorityQueue<> hq = new PriorityQueue<>(Collections.reverseOrder());

 

 

우선순위 큐에 데이터 삽입, 삭제, 확인

- 값을 삽입, 제거할 때 O(n)의 시간복잡도 발생.

import java.util.PriorityQueue;

PriorityQueue<> hq = new PriorityQueue<>();

// 삽입
hq.add(1); // 삽입에 성공하면 true 반환
hq.add(10);
hq.offer(100); // 삽입 실패시, 예외발생 

// 삭제
hq.poll(100); 첫번째 값을 제거하고 비어있다면 null 반환
hq.remove(10); // 값이 비어있으면, 에외 발생

// 첫번째 값 체크(반환만 하고, 제거는 X)
hq.peek();  큐가 비어있으면 null 반환
hq.element(); 예외 발생 

// 초기화
hq.clear();

 

우선순위 큐 동작 방식

출처: https://coding-factory.tistory.com/603

 

 

- 리스트 정렬과 우선순위 큐 중에 뭘 써야 더 성능이 좋을까 ??

Arrays.sort()의 경우에는 평균 nlogn, 최악의 경우 n^2의 시간복잡도

Collections.sort()의 경우 평균, 최악 둘다 nlogn

우선순위 큐의 경우에는 정렬된 상태에서 삽입, 삭제 연산이 일어나기 때문에 logn을 유지 !! 

 

 

BOJ 추천문제 
- https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

- https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

- https://www.acmicpc.net/problem/22252

22252번: 정보 상인 호석