Priority Queue

우선순위 큐

• 일반적인 큐와 달리 우선순위가 높은 요소가 먼저 나오는 자료구조
• FIFO가 아닌 우선순위가 높은 순서대로 처리

자바에서 우선순위 큐 사용법

1. 기본 사용법(최소 힙)

• 최소 힙(Min Heap) 구조
• 값이 작은 요소가 먼저 나옴
• 주요 메서드
  • offer(E item) : 요소 삽입
  • poll() : 가장 작은 값 제거 및 반환
  • peek() : 가장 작은 값 조회 (제거 x)
• 구현 방법
  • PriorityQueue 클래스

import java.util.PriorityQueue;
 
public class PriorityQueueExample {
    public static void main(String[] args) {
	     // 최소 힙
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        pq.offer(3);
        pq.offer(1);
        pq.offer(4);
        pq.offer(1);
        pq.offer(2);
 
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 1 1 2 3 4 (오름차순 출력)
        }
    }
}

2. 최대 힙

• Comparator 사용하여 최대 힙 구현

방법 1 : Comparator.reverseOrder()

import java.util.PriorityQueue;
import java.util.Collections;
 
public class MaxHeapExample {
    public static void main(String[] args) {
        // 최대 힙
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); 
        
        maxHeap.offer(3);
        maxHeap.offer(1);
        maxHeap.offer(4);
        maxHeap.offer(1);
        maxHeap.offer(2);
 
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 4 3 2 1 1 (내림차순 출력)
        }
    }
}

방법 2 : Comparator 직접 구현

import java.util.PriorityQueue;
import java.util.Comparator;
 
public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>( (a, b) -> b - a ); // 람다식 사용
 
        maxHeap.offer(3);
        maxHeap.offer(1);
        maxHeap.offer(4);
        maxHeap.offer(1);
        maxHeap.offer(2);
 
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 4 3 2 1 1
        }
    }
}