[Java] PriorityQueue

PriorityQueue, java.util.PriorityQueue, Java PriorityQueue, 우선순위큐, 최소힙

정의

java.util.PriorityQueue<E> 는 이진 힙 (binary heap) 기반의 Queue 구현. FIFO 가 아닌 우선순위 순서 로 원소를 꺼낸다.

기본은 min-heap, Comparable 의 자연 순서나 Comparator 로 우선순위 결정. 가장 작은 (또는 highest-priority) 원소가 head.

시각화

내부 구조

public class PriorityQueue<E> extends AbstractQueue<E> ... {
    transient Object[] queue;      // 힙을 표현하는 배열
    private int size;
    private final Comparator<? super E> comparator;
}

배열로 이진 힙을 표현. 인덱스 i 일 때:

• 부모: (i - 1) / 2
• 왼쪽 자식: 2i + 1
• 오른쪽 자식: 2i + 2

배열: [1, 3, 2, 6, 5, 8, 7]
힙:        1
         /   \
        3     2
       / \   / \
      6   5 8   7

peek (= queue[0]) 가 항상 최솟값.

복잡도

작업	시간
offer(e) (add)	O(log n) (sift up)
poll() (remove min)	O(log n) (sift down)
peek()	O(1)
contains	O(n)
remove(Object)	O(n) (선형 검색 + sift)

사용 예

최소값 N 개 (Top-K)

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int x : data) {
    minHeap.offer(x);
    if (minHeap.size() > k) minHeap.poll();   // k 보다 크면 제거
}
// minHeap 에는 최대 k 개의 가장 큰 값들이 들어있음

O(n log k) 로 Top-K 해결. 전체 정렬 O(n log n) 보다 효율적.

작업 스케줄러

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed()   // 우선순위 높은 게 먼저
);
scheduler.offer(new Task(...));
Task next = scheduler.poll();

Dijkstra 알고리즘

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a[1], b[1])   // [node, distance]
);
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    // ... process ...
}

함정

1. 순회 순서가 정렬 순서가 아니다

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 3, 8, 1));
for (Integer x : pq) System.out.print(x + " ");   // 1 3 8 5 (힙 배열 순서)

원소를 정렬된 순서로 보려면 poll() 을 반복하거나 별도 정렬 필요.

2. null 비허용

pq.offer(null);   // NullPointerException

3. thread-safe 가 아님

PriorityBlockingQueue 가 동시성 버전.

4. remove(Object) 는 O(n)

힙에서 임의 원소를 빠르게 찾는 방법이 없다. 빠른 remove 가 필요하면 TreeSet 또는 외부 인덱싱 자료구조.

참고

• Object
• Iterable
• Collection
• Queue
• ArrayDeque
• PriorityBlockingQueue