Java/Java이론

Java의 PriorityQueue: 우선순위 기반 큐

P_eli 2024. 11. 21. 23:02
728x90
반응형

Java의 PriorityQueue는 우선순위에 따라 요소를 관리하고 처리하는 큐입니다. 일반적인 Queue와 달리, 입력 순서가 아닌 요소의 우선순위에 따라 가장 중요한 요소(우선순위가 높은 요소)를 먼저 처리합니다. 기본적으로 오름차순(낮은 값이 높은 우선순위)으로 정렬되지만, 커스터마이징된 Comparator를 사용하여 우선순위 기준을 설정할 수도 있습니다.

 

PriorityQueue의 주요 특징

  1. 우선순위 기반 정렬
    • 기본적으로 오름차순 정렬(숫자가 작을수록 높은 우선순위).
    • 문자열의 경우, 알파벳 순서에 따라 처리.
    • 커스터마이징 가능(예: 내림차순 정렬).
  2. Heap 자료구조 기반
    • 내부적으로 최소 힙(Min-Heap)을 사용하여 우선순위를 유지.
    • 요소를 삽입하거나 삭제하는 작업은 O(log n)의 시간 복잡도를 가짐.
  3. 비동기 안전
    • PriorityQueue는 동기화(synchronized)되지 않음. 여러 스레드에서 사용할 경우 외부적으로 동기화를 추가해야 함.
  4. Null 값 허용 안 됨
    • PriorityQueue는 null 요소를 허용하지 않음.

 

사용 사례

PriorityQueue는 다음과 같은 상황에서 유용합니다:

  • 작업 스케줄링: 우선순위가 높은 작업부터 처리.
  • 최단 경로 알고리즘: 다익스트라 알고리즘에서 최소 비용 정점을 선택.
  • 이벤트 처리 시스템: 시간이 빠른 이벤트부터 처리.

 

PriorityQueue의 기본 사용법

다음은 PriorityQueue의 기본적인 사용 예제입니다.

1. 기본 오름차순 정렬

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // PriorityQueue 생성
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        // 요소 추가
        queue.add(3);
        queue.add(1);
        queue.add(5);
        queue.add(2);

        // 요소 출력
        while (!queue.isEmpty()) {
            System.out.println(queue.poll()); // 1, 2, 3, 5 순서로 출력
        }
    }
}

실행 결과

 

위 코드에서 queue.poll()은 우선순위가 가장 높은 요소(가장 작은 값)를 반환하고 제거합니다.

 

2. 내림차순 정렬

기본 정렬(오름차순) 대신 내림차순으로 정렬하려면, Comparator 를 사용해야 합니다.

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

public class Main2 {
    public static void main(String[] args) {
        // 내림차순 PriorityQueue 생성
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

        // 요소 추가
        queue.add(3);
        queue.add(1);
        queue.add(5);
        queue.add(2);

        // 요소 출력
        while (!queue.isEmpty()) {
            System.out.println(queue.poll()); // 5, 3, 2, 1 순서로 출력
        }
    }
}

 

실행 결과

 

 

주요 메서드 및 설명

메서드 설명
add(E e) 요소를 큐에 추가합니다. 큐의 용량을 초과하면 IllegalStateException이 발생할 수 있습니다.
offer(E e) 요소를 큐에 추가합니다. 용량 초과 시 예외 대신 false를 반환합니다.
poll() 큐에서 우선순위가 가장 높은 요소를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
peek() 우선순위가 가장 높은 요소를 반환하지만, 제거하지는 않습니다. 큐가 비어 있으면 null을 반환합니다.
isEmpty() 큐가 비어 있는지 확인합니다.
size() 큐의 요소 개수를 반환합니다.

 

활용 예제: 작업 스케줄링

우선순위가 설정된 작업 스케줄링 시스템을 구현해 보겠습니다.

import java.util.PriorityQueue;

class Task implements Comparable<Task> {
    String name;
    int priority;

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    // 우선순위에 따른 비교 (낮은 숫자가 높은 우선순위)
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }

    @Override
    public String toString() {
        return "Task{name='" + name + "', priority=" + priority + "}";
    }
}

public class Main {
    public static void main(String[] args) {
        // 작업 스케줄링용 PriorityQueue 생성
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();

        // 작업 추가
        taskQueue.add(new Task("Task A", 3));
        taskQueue.add(new Task("Task B", 1));
        taskQueue.add(new Task("Task C", 2));

        // 작업 처리
        while (!taskQueue.isEmpty()) {
            System.out.println("Processing: " + taskQueue.poll());
        }
    }
}

 

실행 결과

 

마무리

Java의 PriorityQueue는 우선순위가 중요한 작업을 처리할 때 매우 유용합니다. 기본적으로 최소 힙을 사용하여 요소를 관리하며, Comparator를 사용해 우선순위 기준을 자유롭게 설정할 수 있습니다.

이제 다양한 우선순위 기반 문제를 해결하기 위해 PriorityQueue를 활용해 보세요! 😊

728x90
반응형