Priority Queue 우선순위큐

동작 방식

• 요소 삽입: 우선순위 큐에 값을 삽입할 때 해당 값의 우선순위가 큐의 규칙에 따라 저장됩니다.
• 요소 삭제: 우선순위 큐에서 값을 삭제할 때는 큐에 저장된 값 중 가장 높은 우선순위를 가진 값이 먼저 삭제됩니다.

특징

1. 우선순위 기준: 우선순위 큐에서는 각 요소가 우선순위(priority)를 가지고 있으며, 이 우선순위에 따라 처리 순서가 정해집니다.
   • 최대 우선순위 큐: 가장 큰 값(우선순위가 높은 값)이 먼저 처리됩니다.
   • 최소 우선순위 큐: 가장 작은 값(우선순위가 낮은 값)이 먼저 처리됩니다.
2. 내부 구현:
   • 우선순위 큐는 보통 힙(Heap) 자료 구조를 사용하여 구현됩니다. 힙은 완전 이진 트리로, 각 노드의 값이 그 자식 노드보다 크거나 작다는 성질을 가집니다.
   • 최소 힙(min-heap): 부모 노드의 값이 자식 노드의 값보다 작음 (즉, 가장 작은 값이 루트에 위치).
   • 최대 힙(max-heap): 부모 노드의 값이 자식 노드의 값보다 큼 (즉, 가장 큰 값이 루트에 위치).

시간 복잡도

• 삽입: O(log n) (힙 구조를 이용해 요소를 삽입할 때 재배열)
• 삭제: O(log n) (최고 우선순위 요소를 삭제하고 힙을 재정렬)

최소 힙

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // 최소 힙을 이용한 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 값 삽입
        pq.offer(10);
        pq.offer(20);
        pq.offer(15);

        // 우선순위가 가장 높은 값(가장 작은 값) 반환
        System.out.println("최소값: " + pq.peek());  // 출력: 10

        // 우선순위가 가장 높은 값(가장 작은 값) 제거
        System.out.println("제거된 값: " + pq.poll());  // 출력: 10

        // 남은 값 확인
        System.out.println("다음 최소값: " + pq.peek());  // 출력: 15
    }
}

최대힙

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

public class Main {
    public static void main(String[] args) {
        // 최대 힙을 이용한 우선순위 큐
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        maxHeap.offer(10);
        maxHeap.offer(20);
        maxHeap.offer(15);

        System.out.println("최대값: " + maxHeap.peek());  // 출력: 20
        System.out.println("제거된 값: " + maxHeap.poll());  // 출력: 20
        System.out.println("다음 최대값: " + maxHeap.peek());  // 출력: 15
    }
}

우선순위 큐의 활용 예

1. 다익스트라 알고리즘 (Dijkstra's Algorithm): 그래프에서 최단 경로를 찾는 알고리즘에서 우선순위 큐가 사용됩니다.
2. 허프만 코딩 (Huffman Coding): 데이터 압축 알고리즘에서 각 문자의 빈도에 따라 우선순위를 정하고 트리를 생성할 때 우선순위 큐가 사용됩니다.
3. 실시간 작업 스케줄링: 우선순위 큐는 작업의 우선순위에 따라 먼저 처리할 작업을 결정하는 스케줄링 문제에서 유용합니다.