[JAVA] 우선순위 큐

자바의 PriorityQueue 클래스는 우선순위 큐를 구현하는 데 사용된다. 우선순위 큐는 일반적인 큐와 달리 요소들이 우선순위에 따라 정렬되어 관리되며, 우선순위가 높은 요소가 먼저 제거되는 자료구조.

PriorityQueue 클래스의 특징

• 힙(Heap) 기반 구현: PriorityQueue는 내부적으로 힙 자료구조를 사용하여 구현된다. 힙은 완전 이진 트리 형태의 자료구조로, 우선순위가 높은 요소를 효율적으로 관리할 수 있다.
• 자동 정렬: 요소를 추가할 때 자동으로 우선순위에 따라 정렬된다. 기본적으로 작은 값이 높은 우선순위를 가지는 최소 힙(Min Heap)으로 구현된다.
• 사용자 정의 정렬: Comparator 인터페이스를 구현하여 요소의 우선순위를 사용자 정의할 수 있다. 이를 통해 최대 힙 또는 다른 정렬 기준을 적용할 수 있다.

PriorityQueue 클래스의 주요 메서드

• add(element) 또는 offer(element): 큐에 요소를 추가합니다.
• poll(): 큐에서 우선순위가 가장 높은 요소를 제거하고 반환합니다. 큐가 비어있으면 null을 반환합니다.
• remove(): 큐에서 우선순위가 가장 높은 요소를 제거합니다. 큐가 비어있으면 예외를 발생시킵니다.
• peek(): 큐에서 우선순위가 가장 높은 요소를 반환하지만, 제거하지는 않습니다. 큐가 비어있으면 null을 반환합니다.
• isEmpty(): 큐가 비어있는지 확인합니다.
• clear(): 큐의 모든 요소를 제거합니다.
• size(): 큐의 요소 수를 반환합니다.

PriorityQueue 클래스의 사용 예시

Java

 

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 정수형 우선순위 큐 생성 (최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 요소 추가
        pq.add(10);
        pq.add(5);
        pq.add(15);
        pq.add(2);

        // 우선순위가 가장 높은 요소 제거 및 출력
        System.out.println(pq.poll()); // 2

        // 큐의 모든 요소 출력
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 5, 10, 15
        }
    }
}

사용자 정의 정렬 예시

Java

 

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueComparatorExample {
    public static void main(String[] args) {
        // 문자열 길이 기준 우선순위 큐 생성
        PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingInt(String::length));

        // 요소 추가
        pq.add("apple");
        pq.add("banana");
        pq.add("kiwi");

        // 우선순위가 가장 높은 요소 제거 및 출력
        System.out.println(pq.poll()); // kiwi

        // 큐의 모든 요소 출력
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // apple, banana
        }
    }
}

PriorityQueue 클래스의 활용

PriorityQueue는 다양한 알고리즘 및 문제 해결에 유용하게 활용됩니다.

• 다익스트라 알고리즘: 최단 경로를 찾는 데 사용됩니다.
• 허프만 코딩: 데이터 압축 알고리즘에 사용됩니다.
• 작업 스케줄링: 작업의 우선순위에 따라 스케줄링하는 데 사용됩니다.