우선순위 큐 (Priority Queue)

우선순위 큐

• 모든 데이터에 우선 순위가 있음
• 우선순위가 높은 데이터가 먼저 나옴 (선입선출 FIFO가 아님)
• Dequeue시, 우선순위가 높은 순으로 나감
• 우선순위가 같은 경우에는 선입선출
• PriorityQueue클래스를 이용하여 우선순위 큐를 구현

우선순위 큐(Priority Queue)는 데이터를 우선순위에 따라 저장하고 처리하는 자료구조이다.
각 요소(element)는 우선순위(priority)와 함께 저장되며, 우선순위가 높은 요소가 먼저 처리된다.

우선순위 큐는 보통 힙(heap) 자료구조를 이용하여 구현된다. 힙은 이진트리의 일종으로, 부모노드와 자식노드 간에 우선순위가 존재하는 자료구조이다. 최대 힙(max heap)에서는 부모노드의 우선순위가 자식노드의 우선순위보다 높아야 하며, 최소 힙(min heap)에서는 그 반대가 된다.

우선순위 큐 기본 연산

삽입(insertion): 우선순위가 있는 새로운 요소를 큐에 삽입합니다.
삭제(deletion): 우선순위가 가장 높은 요소를 큐에서 제거합니다.
검색(peeking): 우선순위가 가장 높은 요소를 확인합니다.

우선순위 큐 사용시기

1. 그래프 알고리즘에서 최소 신장 트리(Minimum Spanning Tree)를 찾는 Prim 알고리즘 등에서 사용된다. (최소신장트리:그래프의 최소연결부분=간선수가 제일 적은 부분)
2. 다익스트라(Dijkstra) 알고리즘 등에서 최단 경로를 찾는 데 사용된다.
3. 시뮬레이션 시스템에서 이벤트 처리 등에 사용됩니다.

🌌기본 예제소스

import java.util.*;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Integer를 저장하는 기본적인 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(3);
        pq.add(1);
        pq.add(5);
        pq.add(2);
        pq.add(4);

        // 우선순위가 높은 순서대로 출력됨
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 1 2 3 4 5
        }

        // String을 저장하는 우선순위 큐
        PriorityQueue<String> pq2 = new PriorityQueue<>();

        pq2.add("apple");
        pq2.add("banana");
        pq2.add("pear");
        pq2.add("orange");

        // 알파벳 순서대로 출력됨
        while (!pq2.isEmpty()) {
            System.out.println(pq2.poll()); // apple banana orange pear
        }
        
        PriorityQueue<String> pq3 = new PriorityQueue<>(Collections.reverseOrder());

        pq3.add("apple");
        pq3.add("banana");
        pq3.add("pear");
        pq3.add("orange");

        // 알파벳 순서대로 역순으로 출력됨
        while (!pq3.isEmpty()) {
            System.out.println(pq3.poll()); // pear orange banana apple
        }
    }
}