기준

PriorityQueue는 peek만 빠르다. 넣고 빼는 순간에는 힙 재정렬이 일어나므로 삽입/삭제 비용과 내부 객체 변경을 같이 본다.

사례 지도

장면실수다음 기준
N번 삽입/삭제O(N)으로 계산add, poll은 O(log N)
객체 우선순위 수정PQ가 자동 재정렬된다고 생각제거 후 재삽입 또는 새 객체 삽입
최대 힙b - a Comparator 사용Integer.compare(b, a)
N번째 큰 수모든 값을 저장크기 N 최소 힙 유지
flowchart TD Need["가장 큰 값 또는 작은 값이 계속 필요한가"] --> YesNo{"계속 필요"} YesNo -->|아니오| Sort["정렬 또는 한 번 순회 검토"] YesNo -->|예| Size{"필요한 값 개수가 제한되는가"} Size -->|예| Fixed["고정 크기 PQ 유지"] Size -->|아니오| Full["전체 PQ 가능"] Fixed --> Cost["각 add poll 비용은 log N"] Full --> Cost

add()와 poll()을 O(1)로 착각

발생 장면

BOJ1927 최소 힙에서 N번 반복하므로 전체를 O(N)으로 계산했다.

for (int i = 0; i < n; i++) {
    pq.add(input); // O(log N)
    pq.poll();     // O(log N)
}

힙은 삽입/삭제 때 위아래로 재정렬한다. 전체는 O(N log N)이다.

상세: 자료구조 연산 복잡도 착각

내부 객체 값을 바꾸고 그대로 둠

증상

PQ 안에 들어간 객체의 우선순위 필드를 바꿨는데 꺼내는 순서가 바뀌지 않는다.

PQ는 들어온 시점의 비교 결과로 힙을 만든다. 내부 객체 필드를 수정해도 자동으로 재정렬하지 않는다.

고치는 기준

pq.remove(node);
node.cost = nextCost;
pq.offer(node);

또는 변경된 상태를 새 객체로 넣고, 꺼낼 때 오래된 상태를 무시한다.

상세: PQ 내부 객체 수정 후 재삽입 누락

최대 힙 Comparator에서 오버플로우

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

값 범위가 크면 b - a가 오버플로우될 수 있다.

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

모든 값을 저장해서 메모리를 씀

N번째 큰 수처럼 필요한 것은 상위 N개뿐인데 전체 값을 저장하면 메모리가 커진다.

flowchart LR Input["새 값"] --> Add["PQ에 넣기"] Add --> Over{"크기가 N 초과"} Over -->|예| Poll["가장 작은 값 제거"] Over -->|아니오| Keep["유지"] Poll --> Answer["PQ top이 N번째 큰 수"] Keep --> Answer

관련: 백준 언어 버전별 메모리 제한