[자료구조] Java에서 우선순위 큐 (Priority Queue) 활용하기

오늘은 우선순위 큐에 대해서 포스팅 해보려고 한다. 우선순위 큐 같은 경우에는 개발할 때는 사용한 적이 없다. 하지만 코딩테스트를 풀다보면 우선순위 큐를 사용하는 것을 많이 볼 수 있다. 그래서 오늘은 우선순위 큐의 세세한 내용보다 활용 방법 위주로 포스팅할 것이다.

1. 우선순위 큐(Priority Queue)

---

1-1. 우선순위 큐란?

✅ 우선 Queue라는 것은 FIFO 형태의 자료구조로 먼저 들어간 값이 먼저 나오는 자료구조이다.

그렇다면 우선순위 큐는 무엇일까? 뭔가에 우선순위를 두고 값이 결정되는 것일까? 우선순위 큐의 개념을 알아보자.

우선순위 큐 (Priority Queue)
데이터의 '우선순위'에 따라 정렬되어 관리되는 큐로 단순한 순서보다 '중요도'에 따라 처리 순서가 달라질때 사용

1-2. 우선순위 큐의 특징

PriorityQueue는 내부적으로 힙(Heap) 자료구조를 기반으로 한다.

• 요소들은 자연 정렬 순서(natural ordering) 또는 생성 시 지정한 Comparator 에 따라 정렬
• null 값은 허용되지 않습니다.
• 비교가 불가능한 타입(Comparable을 구현하지 않거나, Comparator가 없는 경우`)은 저장할 수 없음

즉, PriorityQueue는 정렬된 순서를 자동으로 유지하는 큐이다.
이를 직접 구현하려면 매번 정렬 연산이 필요하지만, PriorityQueue는 내부적으로 힙 연산(O(logN)) 을 통해 자동으로 순서를 유지한다.

2. 우선순위 큐 사용법

---

2-1. 우선순위 큐 선언 방법

// 1. 오름차순 (기본값)
PriorityQueue<Integer> pq1 = new PriorityQueue<>();

// 2. 내림차순 (최대 힙) : String, Character 에서도 적용 가능
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Comparator.reverseOrder());

기본은 오름차순(작은 값이 먼저 나옴)이며, Comparator.reverseOrder()를 사용하면 내림차순(큰 값이 먼저 나옴)으로 바뀜

그렇다면 사용자 자료형, 즉 클래스를 만들어서 우선순위 큐를 사용해보자.

import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) {
        PriorityQueue<Student> students = new PriorityQueue<>(
                (a, b) -> {
                    if (a.math != b.math) return b.math - a.math;  // math 기준 내림차순
                    return b.english - a.english;                  // english 기준 내림차순
                }
        );

        students.offer(new Student(90, 100));
        students.offer(new Student(10, 80));
        students.offer(new Student(30, 80));

        System.out.println(students.peek().math); // 90 출력
        System.out.println(students.peek().english); // 100 출력
    }

    static class Student {
    
        int math;
        int english;

        public Student(int math, int english) {
            this.math = math;
            this.english = english;
        }
        
    }
}

위에처럼 Student 클래스에 우선순위를 주는 방법이 있고, 밑에처럼 Comparable를 직접 구현해서 우선순위를 결정하는 방법이 있다.

static class Student implements Comparable<Student> {

	int math;
    int english;

    public Student(int math, int english) {
    	this.math = math;
        this.english = english;
    }
    
    @Override
    public int compareTo(Student student){
    	return this.math - student.math;
    }
    
}

2-2. 자주 사용되는 메소드

메서드	설명
offer(E e)	큐에 요소를 추가합니다. (성공 시 true 반환)
poll()	큐의 가장 우선순위가 높은 요소를 제거하고 반환합니다. 비어있으면 null 반환
remove()	큐의 요소를 제거합니다. (비어있으면 NoSuchElementException 발생)
peek()	큐의 가장 우선순위가 높은 요소를 반환만 합니다. (삭제 X)
element()	큐의 첫 번째 요소를 반환합니다. (비어있으면 NoSuchElementException)
size()	큐에 저장된 요소의 개수를 반환합니다.

출처

• 우선순위 큐 Java 17 문서