10. 자료구조-PriorityQueue

자료구조 - PriorityQueue

Summary

계속 최솟값/최댓값을 꺼내야 하면 PriorityQueue를 쓴다.
정렬 한 번으로 끝나는 문제인지, 매번 최소/최대가 바뀌는 문제인지 구분한다.

---

강의실 배정형 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] lectures = new int[n][2];
 
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            lectures[i][0] = Integer.parseInt(st.nextToken());
            lectures[i][1] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(lectures, (a, b) -> {
            if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
            return Integer.compare(a[0], b[0]);
        });
 
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] lecture : lectures) {
            int start = lecture[0];
            int end = lecture[1];
 
            if (!pq.isEmpty() && pq.peek() <= start) {
                pq.poll();
            }
            pq.offer(end);
        }
 
        System.out.println(pq.size());
    }
}

---

기본형

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
 
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));

---

주의점

실수	주의
기본이 최대힙이라고 착각	Java PriorityQueue 기본은 최소힙
Comparator에서 a - b	overflow 가능. compare 사용
객체 기준 없음	Node/배열 정렬 기준 지정
중간 원소 삭제	PQ는 임의 삭제가 느림

---

백지 복원

1. Java PriorityQueue 기본은 최소힙인가 최대힙인가?
2. 최대힙을 만드는 방법은?
3. Comparator에서 빼기 연산을 피해야 하는 이유는?