PriorityQueue

tryoo0607·2025년 8월 6일

Java 알고리즘 자료구조

Java - 알고리즘/자료구조

목록 보기

4/10

들어가며

알고리즘 공부 중에 새롭게 알게 된 자료구조인 Priority Queue에 대해 정리했습니다.

PriorityQueue (우선순위 큐)

특징

Queue 인터페이스를 구현한 클래스
요소가 삽입될 때 자연 순서(Natural Ordering) 또는 Comparator에 의해 자동 정렬됨
일반적인 FIFO(선입선출) 큐와 달리, 우선순위가 가장 높은 요소가 먼저 꺼내짐
내부적으로 힙(Heap) 자료구조를 기반으로 구현됨 (기본은 최소 힙, 즉 가장 작은 값이 우선)

동작 원리

삽입: offer(E e) → 요소가 우선순위에 맞게 배치됨
삭제: poll() → 가장 높은 우선순위(최소값/Comparator 기준 최우선) 요소를 꺼냄
조회: peek() → 가장 높은 우선순위 요소 확인 (삭제 X)

차이점 (다른 Queue와 비교)

일반 Queue: 삽입한 순서(FIFO)에 따라 처리
PriorityQueue: 삽입 순서와 관계없이 우선순위 기준으로 처리
Deque: 양쪽에서 입출력이 자유롭지만, 우선순위 개념 없음
PriorityQueue: 한쪽에서만 삽입/삭제 가능하지만, 우선순위 기반 정렬 기능 제공

제한 / 주의사항

null 요소 저장 불가
동기화 지원 안 함 (멀티스레드 환경에서는 PriorityBlockingQueue 사용)
내부 순회 시 정렬된 순서가 아님
→ iterator()로 전체를 조회하면 우선순위 순서대로 보장되지 않음
(정렬된 결과가 필요하면 poll()로 하나씩 꺼내야 함)

주요 생성자

PriorityQueue() → 기본(자연 순서)
PriorityQueue(Comparator<? super E> comparator) → 사용자 정의 정렬 기준 지정 가능

활용 예시

작업 스케줄링 (긴급도/우선순위 높은 작업 먼저 실행)
최단 경로 알고리즘 (다익스트라, A* 등)
시뮬레이션(이벤트 처리 순서 관리)

구현 예시

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Comparator;

public class QueueExample {
    public static void main(String[] args) {

        // ================================
        // 1. 일반 Queue (FIFO)
        // ================================
        Queue<Integer> normalQueue = new LinkedList<>();

        normalQueue.offer(3);
        normalQueue.offer(1);
        normalQueue.offer(2);

        System.out.println("일반 Queue (FIFO):");
        while (!normalQueue.isEmpty()) {
            System.out.print(normalQueue.poll() + " ");
        }
        // 출력: 3 1 2   (삽입 순서 그대로)


        // ================================
        // 2. PriorityQueue (기본: 최소 힙)
        // ================================
        Queue<Integer> minHeapQueue = new PriorityQueue<>();

        minHeapQueue.offer(3);
        minHeapQueue.offer(1);
        minHeapQueue.offer(2);

        System.out.println("\n\nPriorityQueue (Min Heap, 기본):");
        while (!minHeapQueue.isEmpty()) {
            System.out.print(minHeapQueue.poll() + " ");
        }
        // 출력: 1 2 3   (값이 작은 순)


        // ================================
        // 3. PriorityQueue (최대 힙, Comparator 사용)
        // ================================
        Queue<Integer> maxHeapQueue = new PriorityQueue<>(Comparator.reverseOrder());

        maxHeapQueue.offer(3);
        maxHeapQueue.offer(1);
        maxHeapQueue.offer(2);

        System.out.println("\n\nPriorityQueue (Max Heap, Comparator):");
        while (!maxHeapQueue.isEmpty()) {
            System.out.print(maxHeapQueue.poll() + " ");
        }
        // 출력: 3 2 1   (값이 큰 순)
    }
}