• 우선순위가 가장 높은 요소가 먼저 나오는 자료구조
• 각 요소는 우선순위와 함께 저장되며, 삽입 순서와 상관없이 우선순위에 따라 요소가 추출
• 이미지 출처: 나노 바나나 프로 (Nano Banana Pro)

특징

• 우선순위가 높은 데이터가 먼저 나옴
• 힙(Heap) 자료구조로 구현되는 것이 일반적
• 시간 복잡도:
  • 삽입: O(log n)
  • 최대/최소값 확인: O(1)
  • 최대/최소값 추출: O(log n)

문제 유형

• 다익스트라 알고리즘 (최단 경로)
• 프림 알고리즘 (최소 신장 트리)
• 허프만 코딩 (압축 알고리즘)
• 작업 스케줄링
• 이벤트 시뮬레이션

코드 예시

(1) 자바 구현

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

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 최소 힙(Min Heap) - 기본값
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 최대 힙(Max Heap)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        // 삽입
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);
        
        // 최솟값 확인 (제거하지 않음)
        System.out.println("최솟값: " + minHeap.peek()); // 1
        
        // 요소 추출 (우선순위가 가장 높은 요소)
        System.out.println("추출: " + minHeap.poll()); // 1
        System.out.println("추출: " + minHeap.poll()); // 2
        System.out.println("추출: " + minHeap.poll()); // 5
        System.out.println("추출: " + minHeap.poll()); // 8
    }
}

(2) 사용자 정의 객체에 대한 우선순위 설정

import java.util.PriorityQueue;

class Person implements Comparable<Person> {
    String name;
    int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int compareTo(Person other) {
        // 나이가 적은 순서대로 정렬
        return this.age - other.age;
    }
    
    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

public class CustomPriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Person> pq = new PriorityQueue<>();
        
        pq.offer(new Person("Alice", 25));
        pq.offer(new Person("Bob", 21));
        pq.offer(new Person("Charlie", 30));
        
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
        // Bob(21)
        // Alice(25)
        // Charlie(30)
    }
}

(3) Comparator를 이용한 우선순위 설정

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

class Student {
    String name;
    int score;
    
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    @Override
    public String toString() {
        return name + "(" + score + ")";
    }
}

public class ComparatorExample {
    public static void main(String[] args) {
        // 점수가 높은 학생이 우선순위를 갖도록 설정
        PriorityQueue<Student> pq = new PriorityQueue<>(
            (s1, s2) -> s2.score - s1.score
        );
        
        pq.offer(new Student("Alice", 85));
        pq.offer(new Student("Bob", 92));
        pq.offer(new Student("Charlie", 78));
        
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
        // Bob(92)
        // Alice(85)
        // Charlie(78)
    }
}

코딩 테스트 예제: K번째 큰 요소 찾기

import java.util.PriorityQueue;

public class KthLargestElement {
    public static int findKthLargest(int[] nums, int k) {
        // 최소 힙으로 k개의 요소만 유지
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int num : nums) {
            pq.offer(num);
            
            if (pq.size() > k) {
                pq.poll(); // k개 이상이면 최소값 제거
            }
        }
        
        return pq.peek(); // k번째 큰 요소
    }
    
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println(k + "번째 큰 요소: " + findKthLargest(nums, k)); // 5
    }
}