[JAVA] PriorityQueue 설명 및 사용법

PriorityQueue는 자바에서 제공하는 우선순위 큐(Priority Queue) 구현체로, 요소를 우선순위에 따라 자동으로 정렬하여 관리하는 자료구조입니다. 내부적으로 힙(Heap) 자료구조를 기반으로 하며, 최소 힙(Min-Heap)을 기본으로 사용합니다.

---

1. 🌐 PriorityQueue란?

1.1 주요 특징

• 자동 정렬: 삽입된 요소는 우선순위에 따라 정렬됩니다.
  (기본적으로 오름차순으로 정렬되며, 사용자 정의 정렬 순서를 지정할 수 있습니다.)
• FIFO가 아닌 우선순위 기반 처리:
  • 일반적인 큐(FIFO)와 다르게, 요소는 우선순위가 높은 순서대로 처리됩니다.
• 중복 요소 허용:
  • 동일한 값을 여러 번 삽입할 수 있습니다.
• 내부적으로 힙(Heap) 자료구조를 사용하여 정렬 및 삽입/삭제 작업을 효율적으로 수행합니다.

---

2. 📋 PriorityQueue 주요 메서드

메서드	설명
add(E e)	큐에 요소 삽입 (성공 시 true 반환, 실패 시 예외 발생)
offer(E e)	큐에 요소 삽입 (성공 시 true 반환, 실패 시 false 반환)
poll()	우선순위가 가장 높은 요소를 제거하고 반환 (큐가 비어 있으면 null)
remove()	우선순위가 가장 높은 요소를 제거하고 반환 (큐가 비어 있으면 예외)
peek()	우선순위가 가장 높은 요소를 조회 (큐가 비어 있으면 null)
element()	우선순위가 가장 높은 요소를 조회 (큐가 비어 있으면 예외)

---

3. 🎯 PriorityQueue 기본 사용법

3.1 기본 우선순위 (오름차순)

PriorityQueue는 기본적으로 요소를 오름차순으로 정렬합니다. 즉, 숫자가 작은 값이 가장 높은 우선순위를 가집니다.

코드 예제

import java.util.PriorityQueue;

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

        // 요소 삽입
        queue.add(30);
        queue.add(10);
        queue.add(20);

        // 우선순위가 가장 높은 요소부터 제거
        System.out.println(queue.poll()); // 출력: 10
        System.out.println(queue.poll()); // 출력: 20
        System.out.println(queue.poll()); // 출력: 30
    }
}

결과

요소가 10, 20, 30 순서로 정렬되어 반환됩니다.

---

3.2 사용자 정의 정렬

우선순위를 직접 정의하려면 Comparator를 제공해야 합니다. 예를 들어, 내림차순 또는 사용자 정의 객체를 기준으로 정렬할 수 있습니다.

---

내림차순 정렬

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

public class PriorityQueueDescendingExample {
    public static void main(String[] args) {
        // 내림차순 정렬
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

        // 요소 삽입
        queue.add(30);
        queue.add(10);
        queue.add(20);

        // 출력
        while (!queue.isEmpty()) {
            System.out.println(queue.poll()); // 30, 20, 10
        }
    }
}

---

사용자 정의 객체 정렬

예를 들어, 학생 객체(Student)를 점수(grade)에 따라 정렬한다고 가정해 봅시다.

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

class Student {
    String name;
    int grade;

    public Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }

    @Override
    public String toString() {
        return name + " (" + grade + ")";
    }
}

public class PriorityQueueCustomObjectExample {
    public static void main(String[] args) {
        // 점수(grade) 오름차순 정렬
        PriorityQueue<Student> queue = new PriorityQueue<>(Comparator.comparingInt(s -> s.grade));

        // 학생 데이터 삽입
        queue.add(new Student("Alice", 85));
        queue.add(new Student("Bob", 92));
        queue.add(new Student("Charlie", 78));

        // 출력
        while (!queue.isEmpty()) {
            System.out.println(queue.poll()); // Charlie (78), Alice (85), Bob (92)
        }
    }
}

내림차순으로 사용자 정의 객체 정렬

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

public class PriorityQueueDescendingCustomObjectExample {
    public static void main(String[] args) {
        // 점수(grade) 내림차순 정렬
        PriorityQueue<Student> queue = new PriorityQueue<>((s1, s2) -> s2.grade - s1.grade);

        // 학생 데이터 삽입
        queue.add(new Student("Alice", 85));
        queue.add(new Student("Bob", 92));
        queue.add(new Student("Charlie", 78));

        // 출력
        while (!queue.isEmpty()) {
            System.out.println(queue.poll()); // Bob (92), Alice (85), Charlie (78)
        }
    }
}

---

4. 🛠️ 내부 동작 원리

4.1 힙(Heap) 자료구조

PriorityQueue는 내부적으로 힙(Heap) 자료구조를 사용하여 요소를 정렬합니다.

• 기본 구현은 최소 힙(Min-Heap)으로, 루트 노드가 가장 작은 값을 가집니다.
• 삽입(add)과 삭제(poll) 시, 힙의 성질을 유지하기 위해 O(log n) 시간 복잡도를 가집니다.

---

5. 🔍 제한 사항 및 주의점

5.1 요소의 순서 보장

• PriorityQueue는 삽입 순서를 유지하지 않습니다.
• 오직 우선순위에 기반하여 요소를 정렬하고 처리합니다.

5.2 중간 요소 접근

• 특정 인덱스에 있는 요소를 조회하거나 삭제할 수 없습니다.
• 큐의 가장 높은 우선순위 요소만 peek() 또는 poll()로 접근 가능합니다.

5.3 정렬 방식

• 기본 정렬은 자연 정렬 순서(오름차순)이며, 사용자 정의 Comparator로 변경할 수 있습니다.

---

6. ⚡ PriorityQueue와 다른 큐 구현체 비교

구현체	내부 구조	삽입/삭제 성능	요소 정렬	FIFO	LIFO	우선순위 기반
PriorityQueue	힙	O(log n)	✅	❌	❌	✅
ArrayDeque	배열	O(1)	❌	✅	✅	❌
LinkedList	연결 리스트	O(1)	❌	✅	✅	❌

---

7. 💡 요약 및 활용 사례

1. 단순 우선순위 작업:
   • 기본 우선순위 정렬이 필요한 경우 PriorityQueue를 사용하세요.
2. 사용자 정의 정렬:
   • Comparator를 활용하여 원하는 정렬 기준을 구현하세요.
3. 활용 사례:
   • 작업 스케줄링
   • 최단 경로 알고리즘(예: 다익스트라)
   • 데이터 스트림 처리

💡 PriorityQueue는 우선순위가 중요한 모든 상황에서 효율적으로 활용할 수 있는 자료구조입니다.