Java Academy · 강의

정렬된 처리를 위한 PriorityQueue

작업 일정 관리 상황에서 자연스러운 순서와 사용자 정의 비교자를 사용해 PriorityQueue를 다룹니다.

정렬된 처리를 위한 PriorityQueue은(는) CoddyKit의 무료 Java Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Java Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

PriorityQueue란 무엇인가요?

PriorityQueue는 기본적으로 최소 힙입니다. 자연 순서가 가장 앞선 요소가 항상 헤드에 위치합니다. 요소 전체가 내부적으로 정렬되는 것은 아니며, 최솟값만 앞에 있다는 것이 보장됩니다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (min)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

내부 힙 구조

PriorityQueue는 배열에 저장된 이진 최소 힙을 사용합니다. 인덱스 i의 부모는 항상 2i+1 및 2i+2의 자식보다 작거나 같습니다. 따라서 offer/poll은 O(log n), peek은 O(1)이 됩니다.

반전된 Comparator를 사용한 최대 힙

최대 힙(가장 큰 요소가 먼저 나오는 힙)을 만들려면 Comparator.reverseOrder()를 전달합니다.

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(50);
maxPQ.offer(30);

System.out.println(maxPQ.poll()); // 50 (max)
System.out.println(maxPQ.poll()); // 30

사용자 정의 객체를 사용하는 PriorityQueue

사용자 정의 레코드나 클래스의 순서를 정하려면 comparator를 사용합니다.

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority) // ascending priority
);
queue.offer(new Job("Backup", 5));
queue.offer(new Job("Alert", 1));
queue.offer(new Job("Report", 3));

System.out.println(queue.poll().name()); // Alert (priority 1)

Peek과 Poll 비교

peek()은 헤드 요소를 제거하지 않고 반환합니다. poll()은 요소를 제거한 후 반환합니다. 둘 다 빈 큐에서는 null을 반환합니다. 반면 element()/remove()는 예외를 발생시킵니다.

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("banana");
pq.offer("apple");

System.out.println(pq.peek()); // apple (not removed)
System.out.println(pq.peek()); // apple (still there)
System.out.println(pq.poll()); // apple (removed)
System.out.println(pq.peek()); // banana

작업 스케줄링 예시

PriorityQueue는 작업마다 우선순위가 다른 CPU 스케줄링 시뮬레이션에 적합합니다.

record Task(String name, int priority) {}

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
scheduler.offer(new Task("Low", 1));
scheduler.offer(new Task("Critical", 10));
scheduler.offer(new Task("Normal", 5));

while (!scheduler.isEmpty()) {
    System.out.println("Processing: " + scheduler.poll().name());
}
// Critical, Normal, Low

K개의 최솟값 요소

PriorityQueue는 배열 전체를 정렬하지 않고 K개의 최솟값 요소를 찾을 때 사용하는 대표적인 도구입니다.

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) pq.offer(n);

for (int i = 0; i < k; i++) {
    System.out.print(pq.poll() + " ");
}
// 1 2 3

최대 힙으로 K개의 최댓값 요소 찾기

또는 순회하는 동안 크기가 K인 최소 힙을 유지하여 K개의 최댓값을 찾을 수 있습니다.

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
// minHeap now contains the 3 largest: [7, 8, 9]
System.out.println(minHeap); // order may vary

Dijkstra 알고리즘 패턴

Dijkstra 최단 경로 알고리즘은 방문하지 않은 노드 중 비용이 가장 낮은 노드를 항상 먼저 확장하기 위해 최소 힙을 사용합니다.

record Entry(int node, int cost) {}

PriorityQueue<Entry> pq = new PriorityQueue<>(
    Comparator.comparingInt(Entry::cost)
);
pq.offer(new Entry(0, 0)); // start node, cost 0

while (!pq.isEmpty()) {
    Entry curr = pq.poll();
    System.out.println("Visit node " + curr.node() + " cost=" + curr.cost());
    // expand neighbors...
}

순회 순서는 정렬되지 않음

PriorityQueue를 순회해도 우선순위 순서로 요소가 반환되지는 않습니다. 우선순위 순서를 보장하는 것은 poll()뿐입니다. 정렬된 출력을 얻으려면 for-each 대신 반복해서 poll해야 합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,3,1,4,2));

// WRONG for sorted output:
for (int n : pq) System.out.print(n+" "); // unordered!

// CORRECT:
while (!pq.isEmpty()) System.out.print(pq.poll()+" "); // 1 2 3 4 5

성능 요약

PriorityQueue 연산의 복잡도:

offer(e): O(log n)
poll(): O(log n)
peek(): O(1)
포함(e): O(n)
제거(e): O(n)

스레드 안전하지 않으므로 동시 접근에는 PriorityBlockingQueue를 사용합니다.

빠른 확인

for-each 반복문으로 PriorityQueue를 순회할 때 요소 순서에 대해 무엇이 보장되나요?

복습: PriorityQueue

핵심 내용:

PriorityQueue는 최소 힙이므로 가장 작은 요소가 먼저 poll됩니다
최대 힙에는 Comparator.reverseOrder()를 사용합니다
offer/poll은 O(log n), peek은 O(1)입니다
대표적인 사용 사례는 K번째 최댓값/최솟값 찾기, Dijkstra, 작업 스케줄링입니다
for-each는 우선순위 순서를 제공하지 않으므로 poll()을 사용합니다

자주 묻는 질문

“정렬된 처리를 위한 PriorityQueue” 강의는 무료인가요?

네 — “정렬된 처리를 위한 PriorityQueue” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Java Academy 강의 전체를 잠금 해제할 수 있습니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“정렬된 처리를 위한 PriorityQueue”에서 뭘 배우나요?

작업 일정 관리 상황에서 자연스러운 순서와 사용자 정의 비교자를 사용해 PriorityQueue를 다룹니다. 브라우저에서 직접 실행하는 실습 코드로 Java Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Java Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Java Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“정렬된 처리를 위한 PriorityQueue” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Java Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Java Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← Java Academy(으)로 돌아가기