PriorityQueue 순회는 정렬 순서가 아니다

PriorityQueue에 값을 넣고 for나 스트림으로 순회하면 정렬된 순서로 나올 것 같지만 아닙니다. 공식 문서는 iterator()와 spliterator()가 큐의 원소를 어떤 특정 순서로도 순회한다고 보장하지 않는다고 명시합니다. 내부가 힙(heap) 구조라 부모가 자식보다 우선순위가 높을 뿐, 같은 레벨끼리는 정렬돼 있지 않기 때문입니다.

정렬 순서가 필요하면 poll()로 하나씩 꺼내야 합니다. head는 지정한 순서 기준 가장 작은 원소이고, poll/peek이 그 head에 접근합니다. 다만 poll()은 원소를 제거하므로 큐가 비게 됩니다. 원본을 유지한 채 정렬 순회만 하고 싶으면 문서 권장대로 Arrays.sort(pq.toArray())를 쓰면 됩니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3); pq.add(1); pq.add(2);

// 정렬 순서 보장 안 됨 (내부 배열 순서로 나올 수 있음)
for (int x : pq) System.out.print(x + " ");

// 정렬 순서로 꺼내기 (큐가 비워짐)
while (!pq.isEmpty()) System.out.print(pq.poll() + " "); // 1 2 3

동점(tie)이면 head가 그중 하나로 임의 결정되니 순서 안정성에 기대면 안 됩니다.

🔗 https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/PriorityQueue.html