[알고리즘] 20. 우선순위 큐(PriorityQueue)

[알고리즘] 20. 우선순위 큐(PriorityQueue)

지난 글에서는 해시셋(HashSet)에 대해 정리했습니다. 이번 글에서는 알고리즘 문제에서 매우 자주 등장하는 자료구조인 우선순위 큐(PriorityQueue)에 대해 알아보겠습니다.

일반 큐는 먼저 들어온 값이 먼저 나가는 구조입니다. 하지만 우선순위 큐는 들어온 순서와 상관없이 우선순위가 높은 값이 먼저 나갑니다.

우선순위 큐는 데이터를 우선순위 기준에 따라 꺼내는 자료구조입니다.

---

1. 우선순위 큐란?

우선순위 큐는 일반 큐처럼 값을 넣고 꺼내는 자료구조입니다. 하지만 값을 꺼낼 때는 먼저 들어온 순서가 아니라, 정해진 우선순위에 따라 값이 나옵니다.

예를 들어 숫자를 우선순위 큐에 넣는다고 생각해보겠습니다.

입력 순서: 30, 10, 20

일반 큐라면 30, 10, 20 순서로 나옵니다. 하지만 Java의 PriorityQueue는 기본적으로 작은 값이 먼저 나오기 때문에 다음 순서로 꺼내집니다.

꺼내는 순서: 10, 20, 30

즉 입력 순서보다 우선순위가 더 중요합니다.

PriorityQueue는 먼저 들어온 값이 아니라, 우선순위가 높은 값을 먼저 꺼냅니다.

---

2. 일반 큐와 우선순위 큐의 차이

일반 큐와 우선순위 큐는 모두 값을 넣고 꺼낼 수 있지만, 꺼내는 기준이 다릅니다.

구분	일반 큐	우선순위 큐
꺼내는 기준	먼저 들어온 순서	우선순위 기준
구조	선입선출	우선순위 기반
대표 사용	BFS, 대기열	최솟값/최댓값 처리, 다익스트라

일반 큐는 순서가 중요할 때 사용하고, 우선순위 큐는 가장 작거나 가장 큰 값을 빠르게 꺼내야 할 때 사용합니다.

---

3. Java에서 PriorityQueue 사용하기

Java에서 우선순위 큐를 사용하려면 PriorityQueue를 import해야 합니다.

import java.util.PriorityQueue;

기본 사용 형태는 다음과 같습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

Integer 값을 저장하는 우선순위 큐입니다. Java의 PriorityQueue는 기본적으로 작은 값이 먼저 나오는 최소 힙 형태로 동작합니다.

Java PriorityQueue의 기본 동작은 작은 값부터 꺼내는 최소 힙입니다.

---

4. offer()로 값 넣기

PriorityQueue에 값을 넣을 때는 offer()를 사용합니다. add()도 사용할 수 있지만, 알고리즘 문제에서는 offer()를 자주 사용합니다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq);

출력 결과는 내부 구조에 따라 다르게 보일 수 있습니다. PriorityQueue는 정렬된 리스트처럼 출력 순서를 보장하지 않습니다.

중요한 것은 출력 모양이 아니라 poll()로 꺼낼 때의 순서입니다.

---

5. poll()로 값 꺼내기

PriorityQueue에서 값을 꺼낼 때는 poll()을 사용합니다. 기본 PriorityQueue에서는 가장 작은 값이 먼저 나옵니다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());

출력 결과는 다음과 같습니다.

10
20
30

30을 먼저 넣었지만 가장 작은 값인 10이 먼저 나왔습니다. 이것이 우선순위 큐의 핵심입니다.

PriorityQueue는 넣은 순서가 아니라 우선순위 기준으로 값을 꺼냅니다.

---

6. peek()으로 가장 우선순위 높은 값 확인하기

peek()은 값을 꺼내지 않고, 현재 가장 먼저 나올 값을 확인만 합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.peek());
System.out.println(pq.peek());
System.out.println(pq.size());

출력 결과는 다음과 같습니다.

10
10
3

peek()은 확인만 하고 제거하지 않기 때문에 여러 번 호출해도 같은 값이 나오고, 크기도 줄어들지 않습니다.

---

7. 최소 힙이란?

Java PriorityQueue의 기본 구조는 최소 힙입니다. 최소 힙은 가장 작은 값이 가장 먼저 나오는 구조입니다.

값 넣기: 50, 10, 30, 20
꺼내기: 10, 20, 30, 50

즉 숫자를 정렬해서 저장하는 것은 아니지만, 값을 꺼낼 때는 항상 가장 작은 값부터 나오도록 관리합니다.

구조	먼저 나오는 값
최소 힙	가장 작은 값
최대 힙	가장 큰 값

기본 PriorityQueue는 최소 힙이므로 최솟값을 빠르게 꺼낼 때 유용합니다.

---

8. 최대 힙 만들기

가장 큰 값을 먼저 꺼내고 싶다면 최대 힙처럼 동작하도록 정렬 기준을 바꿔야 합니다. Java에서는 Collections.reverseOrder()를 사용할 수 있습니다.

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

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());

출력 결과는 다음과 같습니다.

30
20
10

가장 큰 값부터 나오는 최대 힙처럼 동작합니다.

최대 힙이 필요하면 PriorityQueue에 Collections.reverseOrder()를 적용할 수 있습니다.

---

9. PriorityQueue의 기본 연산

PriorityQueue에서 자주 사용하는 연산은 다음과 같습니다.

연산	의미
offer()	값을 넣는다.
poll()	우선순위가 가장 높은 값을 꺼낸다.
peek()	우선순위가 가장 높은 값을 확인한다.
isEmpty()	비어 있는지 확인한다.
size()	저장된 값의 개수를 확인한다.

스택, 큐, 덱과 비슷하게 offer, poll, peek을 사용하지만, PriorityQueue는 꺼내는 기준이 우선순위라는 점이 다릅니다.

---

10. 배열에서 작은 값부터 출력하기

PriorityQueue를 사용하면 배열의 값을 작은 값부터 꺼낼 수 있습니다.

import java.util.PriorityQueue;

int[] numbers = {5, 1, 8, 3, 2};

PriorityQueue<Integer> pq = new PriorityQueue<>();

for (int num : numbers) {
    pq.offer(num);
}

while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

출력 결과는 다음과 같습니다.

1
2
3
5
8

PriorityQueue에 값을 모두 넣은 뒤 poll()을 반복하면 작은 값부터 차례대로 나옵니다.

다만 단순 정렬이 목적이라면 Arrays.sort()를 사용하는 것이 더 직관적일 수 있습니다. PriorityQueue는 중간중간 값을 넣고 꺼내야 하는 상황에서 더 자주 사용됩니다.

---

11. 가장 작은 값 계속 꺼내기

우선순위 큐는 가장 작은 값이나 가장 큰 값을 반복해서 꺼내야 하는 문제에서 유용합니다.

예를 들어 가장 작은 두 값을 꺼내서 더한 뒤 다시 넣는 문제를 생각해볼 수 있습니다. 이런 유형은 카드 정렬, 파일 합치기, 최소 비용 계산 문제에서 자주 등장합니다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(10);
pq.offer(20);
pq.offer(40);

int a = pq.poll();
int b = pq.poll();

int sum = a + b;

pq.offer(sum);

System.out.println(sum);
System.out.println(pq);

출력 결과는 다음과 비슷합니다.

30
[30, 40]

가장 작은 값 10과 20을 꺼내 더한 뒤, 다시 우선순위 큐에 넣었습니다. 이처럼 매번 최솟값을 뽑아야 하는 문제에 PriorityQueue가 잘 맞습니다.

---

12. 문자열 PriorityQueue

PriorityQueue는 숫자뿐 아니라 문자열에도 사용할 수 있습니다. 문자열은 기본적으로 사전순 기준으로 우선순위가 정해집니다.

import java.util.PriorityQueue;

PriorityQueue<String> pq = new PriorityQueue<>();

pq.offer("banana");
pq.offer("apple");
pq.offer("carrot");

while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

출력 결과는 다음과 같습니다.

apple
banana
carrot

문자열은 사전순으로 작은 값부터 나옵니다.

---

13. 객체 우선순위 큐

PriorityQueue는 객체를 저장할 수도 있습니다. 이때는 어떤 기준으로 우선순위를 정할지 Comparator를 만들어야 합니다.

예를 들어 학생 객체를 점수가 낮은 순서로 꺼내보겠습니다.

import java.util.PriorityQueue;

class Student {
    String name;
    int score;

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

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Student> pq = new PriorityQueue<>((a, b) -> a.score - b.score);

        pq.offer(new Student("Kim", 90));
        pq.offer(new Student("Lee", 70));
        pq.offer(new Student("Park", 80));

        while (!pq.isEmpty()) {
            Student student = pq.poll();
            System.out.println(student.name + " " + student.score);
        }
    }
}

출력 결과는 다음과 같습니다.

Lee 70
Park 80
Kim 90

점수가 낮은 학생부터 먼저 나옵니다.

객체를 PriorityQueue에 넣을 때는 우선순위 기준을 반드시 정해야 합니다.

---

14. 여러 조건으로 우선순위 정하기

우선순위 기준이 하나가 아니라 여러 개인 경우도 많습니다. 예를 들어 점수가 낮은 순서로 꺼내되, 점수가 같으면 이름 사전순으로 꺼내고 싶을 수 있습니다.

PriorityQueue<Student> pq = new PriorityQueue<>((a, b) -> {
    if (a.score != b.score) {
        return a.score - b.score;
    }

    return a.name.compareTo(b.name);
});

이 코드는 먼저 점수를 비교합니다. 점수가 다르면 점수가 낮은 학생이 먼저 나옵니다. 점수가 같다면 이름을 사전순으로 비교합니다.

여러 조건이 있다면 1순위 조건을 먼저 비교하고, 같을 때 2순위 조건을 비교합니다.

---

15. PriorityQueue가 사용되는 대표 상황

우선순위 큐는 아래와 같은 상황에서 자주 사용됩니다.

상황	이유
최솟값을 반복해서 꺼내야 할 때	최소 힙으로 빠르게 처리 가능
최댓값을 반복해서 꺼내야 할 때	최대 힙 구성 가능
작업 우선순위 처리	중요도가 높은 작업부터 처리 가능
다익스트라 알고리즘	현재 비용이 가장 작은 노드를 먼저 처리
카드 정렬 / 파일 합치기	가장 작은 두 값을 반복해서 합침

문제를 보고 “가장 작은 값부터 계속 꺼내야 한다” 또는 “우선순위가 높은 것부터 처리해야 한다”는 느낌이 들면 PriorityQueue를 고려할 수 있습니다.

---

16. PriorityQueue의 시간복잡도

PriorityQueue는 내부적으로 힙 구조를 사용합니다. 그래서 값을 넣거나 꺼낼 때 일반 큐보다 비용이 조금 더 듭니다.

연산	시간복잡도
offer()	O(log N)
poll()	O(log N)
peek()	O(1)
size()	O(1)
isEmpty()	O(1)

가장 우선순위가 높은 값을 확인하는 peek()은 O(1)입니다. 하지만 값을 넣거나 꺼내면 힙 구조를 다시 정리해야 하므로 O(log N)이 걸립니다.

PriorityQueue는 삽입과 삭제가 O(log N), 최상단 확인은 O(1)입니다.

---

17. PriorityQueue에서 자주 하는 실수

PriorityQueue를 사용할 때는 아래 실수를 조심해야 합니다.

• PriorityQueue가 전체 정렬된 상태로 저장된다고 생각하는 경우
• 출력된 내부 구조를 보고 정렬이 안 되었다고 착각하는 경우
• 최대 힙이 필요한데 기본 최소 힙을 그대로 사용하는 경우
• 객체를 넣으면서 비교 기준을 만들지 않는 경우
• 비어 있는 PriorityQueue에서 poll()한 값을 바로 사용하는 경우
• a - b 비교에서 큰 수 오버플로우를 고려하지 않는 경우

PriorityQueue는 내부 전체가 정렬된 배열처럼 보장되는 구조가 아닙니다. 정확한 우선순위 순서가 필요하다면 poll()로 하나씩 꺼내 확인해야 합니다.

출력 결과가 정렬되어 보이지 않아도,
poll()로 꺼내면 우선순위 순서대로 나옵니다.

PriorityQueue는 출력 모양보다 poll() 결과가 중요합니다.

---

18. 정리

이번 글에서는 우선순위 큐에 대해 정리했습니다.

• PriorityQueue는 우선순위가 높은 값을 먼저 꺼내는 자료구조이다.
• Java PriorityQueue는 기본적으로 작은 값이 먼저 나오는 최소 힙이다.
• offer()로 값을 넣고, poll()로 우선순위가 높은 값을 꺼낸다.
• peek()은 값을 제거하지 않고 가장 먼저 나올 값을 확인한다.
• 최대 힙은 Collections.reverseOrder()를 이용해 만들 수 있다.
• 문자열은 기본적으로 사전순으로 처리된다.
• 객체를 넣을 때는 Comparator로 우선순위 기준을 정해야 한다.
• offer()와 poll()은 O(log N), peek()은 O(1)이다.

우선순위 큐는 최솟값이나 최댓값을 반복해서 꺼내야 하는 문제에서 강력한 자료구조입니다. 정렬과 비슷해 보일 수 있지만, 중간중간 값을 넣고 꺼내야 할 때 특히 유용합니다.

PriorityQueue의 핵심은 “넣은 순서가 아니라 우선순위 기준으로 꺼낸다”는 점입니다.

---

다음 글 예고

다음 글에서는 힙(Heap)에 대해 알아보겠습니다.

PriorityQueue의 내부 동작과 연결되는 힙 구조, 최소 힙과 최대 힙, 부모와 자식 노드의 관계를 예제로 정리해보겠습니다.