Priority Queue(우선순위 큐)

우선순위 큐(Priority Queue)란?

우선순위 큐(Priority Queue)는 각 요소가 특정 우선순위를 가지며, 가장 높은 우선순위를 가진 요소가 먼저 처리되는 자료 구조입니다. 일반적인 큐(First In, First Out)와는 달리, 요소가 삽입된 순서와 관계없이 우선순위에 따라 요소를 꺼냅니다.

 

우선순위 큐의 특징

1. 정렬된 요소 접근:
   • 기본적으로 최소 힙(Min-Heap) 구조를 사용하여 오름차순으로 요소를 정렬합니다.
   • 요소를 꺼낼 때마다 현재 큐에서 가장 작은 값이 반환됩니다.
2. 시간 복잡도:
   • 삽입(offer) 및 제거(poll) 연산: O(log⁡n)
   • 최댓값 또는 최솟값 조회(peek): O(1)
3. 구현 방식:
   • 내부적으로 이진 힙(Binary Heap)을 기반으로 동작합니다.

 

우선순위 큐

기본 우선순위 큐 (최솟값 기준)

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 요소 추가
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(7);
        
        // 요소 출력 (오름차순)
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 1, 3, 5, 7
        }
    }
}

 

우선순위 큐 (최댓값 기준)

최댓값 기준으로 동작하게 하려면 Comparator를 이용하여 내림차순 정렬을 지정해야 합니다.

import java.util.PriorityQueue;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        // 요소 추가
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(7);
        
        // 요소 출력 (내림차순)
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 7, 5, 3, 1
        }
    }
}