[JAVA] PriorityQueue란 무엇인가? 우선순위 큐의 원리와 실전 활용법

PriorityQueue

 

컴퓨터 과학에서 데이터를 관리하는 가장 기본적인 방법 중 하나는 '줄을 세우는 것(Queue)'입니다. 하지만 현실 세계의 서비스나 복잡한 알고리즘에서는 단순히 '먼저 온 순서(FIFO)'대로 처리하는 것만으로는 부족할 때가 많습니다. 응급실에서 환자를 치료하거나, 운영체제가 프로세스에 CPU 자원을 할당할 때처럼 중요도에 따라 순서가 바뀌어야 하는 상황이 발생하기 때문입니다.

자바의 PriorityQueue는 바로 이러한 문제를 해결하기 위해 탄생했습니다. 이번 글에서는 PriorityQueue의 내부 동작 원리인 '힙(Heap)' 구조부터, 실무에서 성능을 극대화할 수 있는 활용 팁까지 심도 있게 다뤄보겠습니다.

1. PriorityQueue란 무엇인가?

PriorityQueue는 이름 그대로 우선순위가 높은 데이터가 먼저 나가는 큐입니다. 일반적인 Queue 인터페이스를 구현하고 있지만, 내부적으로는 이진 트리 구조의 일종인 힙(Heap)을 사용하여 요소를 정렬합니다.

• 기본 순서: 별도의 설정이 없다면 숫자는 낮은 순서대로, 문자는 알파벳 순서대로(Natural Ordering) 우선순위를 갖습니다.
• 동적 정렬: 요소가 추가되거나 삭제될 때마다 내부적으로 재정렬이 일어나 항상 최상단 노드(Root)에 우선순위가 가장 높은 값이 위치하게 됩니다.

2. 내부 동작의 핵심: 이진 힙(Binary Heap)

PriorityQueue의 성능 비결은 바로 '힙' 구조에 있습니다. 전체 데이터를 완전 정렬 상태로 유지하는 TreeSet과 달리, 힙은 '부모 노드가 자식 노드보다 우선순위가 높다'는 조건만 만족하는 느슨한 정렬 상태를 유지합니다.

이 덕분에 데이터를 추가하거나 삭제할 때의 시간 복잡도는 O(log n)으로 매우 효율적입니다. 단순히 가장 높은 우선순위의 값을 확인하는 작업은 O(1)이면 충분합니다.

3. 실전 활용: 커스텀 정렬(Comparator)

실무에서는 객체 내부의 특정 필드(예: 주문 금액, 마감 시간 등)를 기준으로 우선순위를 정해야 하는 경우가 많습니다. 이때 Comparator를 활용하면 매우 유연하게 설계할 수 있습니다.

// 우선순위가 높은(값이 큰) 순서대로 정렬하는 예제
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

// 객체 기준 커스텀 정렬 예제
PriorityQueue<Task> taskQueue = new PriorityQueue<>((a, b) -> b.getPriority() - a.getPriority());

4. 자료구조 특성 비교 요약

상황에 맞는 최적의 컬렉션을 선택할 수 있도록 주요 특징을 비교해 보았습니다.

비교 항목	Queue (LinkedList)	PriorityQueue	TreeSet
정렬 방식	FIFO (선입선출)	우선순위 기반 힙 정렬	전체 이진 트리 정렬
삽입/삭제 시간	O(1)	O(log n)	O(log n)
중복 허용	허용	허용	불가
Null 허용	허용	불가 (에러 발생)	불가
주요 용도	대기열, 메시지 처리	스케줄링, 최단경로 탐색	범위 검색, 정렬 유지

5. 사용 시 주의사항 (Caveats)

1. 비동기 환경: PriorityQueue는 스레드 안전(Thread-safe)하지 않습니다. 멀티스레드 환경에서는 PriorityBlockingQueue를 사용해야 합니다.
2. 순회 시 정렬 미보장: iterator()를 사용하여 전체 요소를 출력할 때는 힙 구조의 특성상 순서가 뒤섞여 보일 수 있습니다. 반드시 poll()을 통해 하나씩 꺼내야 올바른 우선순위 순서를 얻을 수 있습니다.
3. Null 값 투입: 우선순위를 비교할 대상이 없으므로 NullPointerException이 발생합니다.

6. 결론: 언제 PriorityQueue를 써야 할까?

전체 데이터를 정렬할 필요는 없지만, 최소값이나 최대값을 지속적으로 추출해야 하는 상황에서 PriorityQueue는 최고의 퍼포먼스를 보여줍니다. 다익스트라(Dijkstra) 알고리즘이나 허프만 코딩, 실시간 랭킹 시스템 등을 구현할 때 이 강력한 도구를 적극적으로 활용해 보시기 바랍니다.

---

※ 내용 출처 및 참고 문헌

• Oracle Java Documentation: Class PriorityQueue
• Introduction to Algorithms (Cormen et al.) - Binary Heap Section
• Effective Java 3rd Edition (Joshua Bloch)