Priority Queue 자료구조의 특징

우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
중복: 가능
순서: 우선 순위(default: 올림차순)
정렬: 불가능(힙구조)

PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

1. 높은 우선순위의 요소를 먼저 꺼내서 처리
2. 내부 요소는 힙으로 구성되어 이진트리 구조
3. 힙으로 구성되어 있기에 시간 복잡도는 O(nLog n)
4. null 허용 X

선언

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

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = 
new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = 
new PriorityQueue<>(Collections.reverseOrder());

//람다 함수를 활용하여 int[] 형 우선순위큐(오름차순)
 PriorityQueue<int[]> pq = 
 new PriorityQueue<>((a, b) -> a[0] - a[1]);

// 람다 함수를 활용하여 int[] 형 우선순위큐(오름차순)
            PriorityQueue<int[]> pq = 
            new PriorityQueue<>((a, b) -> {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                } else {
                    return a[1] - b[1];
                }
            });

주요 메소드

• add(Object o): 데이터 추가
• poll(): 헤드를 검색 및 제거(비어 있는 경우 null)
• peek(): 헤드를 검색하지만 제거하지 않음(비어 있는 경우 null)
• remove(Object o): 큐에 저장되어 있다면, 데이터 삭제
• clear(): 데이터 모두 삭제
• size(): 크기(boolean)
• isEmpty(): map 비어있는지 확인
• offer(Object o): 데이터 추가
• poll(Object o): 헤드를 검색 및 제거(비어 있는 경우 null)
• toArray(): 큐의 모든 요소를 포함하는 배열을 리턴
• toArray(T[] a): 큐의 모든 요소를 포함하는 배열을 리턴(타입 지정)

시간 복잡도

offer : O(log n)
peek : O(1)
poll : o(log n)
size : o(1)