우선순위 큐 활용 — Dijkstra, 스케줄러, 이벤트 처리
"다음에 처리할 것"이 항상 가장 중요한(또는 가장 빠른) 것이어야 한다면, 어떤 자료구조를 선택해야 할까요?
우선순위 큐란
우선순위 큐(Priority Queue)는 각 요소에 우선순위 가 있고, 우선순위가 가장 높은 요소가 먼저 나오는 자료구조입니다.
일반 큐가 FIFO(선입선출)라면, 우선순위 큐는 "우선순위순 출" 입니다.
// 일반 큐: 먼저 넣은 것이 먼저 나옴
Queue<String> queue = new LinkedList<>();
// 우선순위 큐: 우선순위가 높은 것이 먼저 나옴
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
pq.poll(); // 1 (가장 작은 값이 먼저)
pq.poll(); // 3
pq.poll(); // 5
Dijkstra 알고리즘 — 최단 경로
우선순위 큐의 가장 대표적인 활용은 Dijkstra 알고리즘 입니다.
문제
가중치가 있는 그래프에서 시작 정점부터 모든 정점까지의 최단 거리를 구합니다.
핵심 아이디어
- 아직 방문하지 않은 정점 중 거리가 가장 짧은 정점 을 선택
- 이 "가장 짧은 정점 선택"을 우선순위 큐로 O(log n)에 처리
구현
public class Dijkstra {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public int[] shortestPath(List<List<Edge>> graph, int start) {
int n = graph.size();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
// {거리, 정점} 쌍으로 최소 힙
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0])
);
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int d = current[0], u = current[1];
// 이미 더 짧은 경로를 찾은 경우 스킵
if (d > dist[u]) continue;
// 인접 정점 탐색
for (Edge edge : graph.get(u)) {
int newDist = dist[u] + edge.weight;
if (newDist < dist[edge.to]) {
dist[edge.to] = newDist;
pq.offer(new int[]{newDist, edge.to});
}
}
}
return dist;
}
}
시간 복잡도
- 배열 탐색 방식: O(V²)
- 우선순위 큐 방식: O((V + E) log V)
정점이 많고 간선이 상대적으로 적은 희소 그래프 에서 우선순위 큐 방식이 훨씬 빠릅니다.
실무 활용
// 네비게이션: 도로 네트워크에서 최단 경로
// API Gateway: 서비스 간 최소 지연 경로 선택
// 네트워크: 라우팅 프로토콜 (OSPF가 Dijkstra 사용)
스레드 스케줄러
Java의 ScheduledThreadPoolExecutor는 내부적으로 힙 기반 큐 를 사용합니다.
DelayedWorkQueue
// ScheduledThreadPoolExecutor 내부 (개념적)
// 실행 시각이 가장 빠른 작업을 먼저 꺼내기 위해 힙 사용
static class DelayedWorkQueue extends AbstractQueue<Runnable> {
private RunnableScheduledFuture<?>[] queue;
// 실행 시각 기준 최소 힙
}
사용 예시
ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(2);
// 5초 후 실행
scheduler.schedule(() -> {
System.out.println("5초 후 실행");
}, 5, TimeUnit.SECONDS);
// 1초 간격으로 반복 실행
scheduler.scheduleAtFixedRate(() -> {
System.out.println("매 1초마다 실행");
}, 0, 1, TimeUnit.SECONDS);
// 이전 작업 완료 후 2초 뒤 실행
scheduler.scheduleWithFixedDelay(() -> {
System.out.println("이전 작업 완료 2초 후 실행");
}, 0, 2, TimeUnit.SECONDS);
내부 동작:
- 작업이 등록되면 실행 시각을 키로 힙에 삽입
- 워커 스레드는 힙의 peek()으로 다음 실행 시각 확인
- 시각이 되면 poll()로 꺼내서 실행
- 반복 작업은 다음 실행 시각으로 다시 힙에 삽입
Spring의 @Scheduled
@Component
public class MetricsCollector {
@Scheduled(fixedRate = 60000) // 1분마다
public void collectMetrics() {
// CPU, 메모리, 디스크 사용량 수집
}
@Scheduled(cron = "0 0 * * * *") // 매시 정각
public void hourlyReport() {
// 시간별 리포트 생성
}
}
// 내부적으로 ScheduledThreadPoolExecutor 사용
// 각 @Scheduled 작업이 힙에 등록됨
타이머 이벤트 시스템
게임 서버나 실시간 시스템에서 타이머 이벤트를 관리할 때 우선순위 큐가 핵심입니다.
public class TimerEventSystem {
static class TimerEvent implements Comparable<TimerEvent> {
long executeAt; // 실행 시각 (밀리초)
Runnable action; // 실행할 작업
String name;
TimerEvent(long executeAt, Runnable action, String name) {
this.executeAt = executeAt;
this.action = action;
this.name = name;
}
@Override
public int compareTo(TimerEvent other) {
return Long.compare(this.executeAt, other.executeAt);
}
}
private final PriorityQueue<TimerEvent> eventQueue = new PriorityQueue<>();
// 이벤트 등록
public void scheduleAfter(long delayMs, Runnable action, String name) {
long executeAt = System.currentTimeMillis() + delayMs;
eventQueue.offer(new TimerEvent(executeAt, action, name));
}
// 이벤트 루프 (단일 스레드 기반)
public void run() {
while (!eventQueue.isEmpty()) {
TimerEvent next = eventQueue.peek();
long now = System.currentTimeMillis();
if (next.executeAt <= now) {
eventQueue.poll();
next.action.run(); // 실행 시각이 됐으면 실행
} else {
// 다음 이벤트까지 대기
long waitTime = next.executeAt - now;
try { Thread.sleep(Math.min(waitTime, 100)); }
catch (InterruptedException e) { break; }
}
}
}
}
Netty의 HashedWheelTimer
Netty는 대량의 타이머를 효율적으로 관리하기 위해 HashedWheelTimer 를 사용합니다. 이것은 힙 기반이 아니라 시간 슬롯 기반이지만, 소규모 타이머에는 PriorityQueue가 더 적합합니다.
K번째 큰 요소 찾기
// 스트리밍 데이터에서 K번째 큰 요소를 실시간으로 유지
public class KthLargest {
private PriorityQueue<Integer> minHeap;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
this.minHeap = new PriorityQueue<>();
for (int num : nums) add(num);
}
public int add(int val) {
minHeap.offer(val);
if (minHeap.size() > k) {
minHeap.poll(); // 크기를 k로 유지
}
return minHeap.peek(); // 힙의 루트가 K번째 큰 값
}
}
// 사용
KthLargest kthLargest = new KthLargest(3, new int[]{4, 5, 8, 2});
kthLargest.add(3); // 4 (k=3번째 큰 값)
kthLargest.add(5); // 5
kthLargest.add(10); // 5
작업 우선순위 처리
@Component
public class TaskProcessor {
static class Task implements Comparable<Task> {
int priority; // 낮을수록 높은 우선순위
Instant createdAt;
Runnable work;
@Override
public int compareTo(Task other) {
int cmp = Integer.compare(this.priority, other.priority);
if (cmp != 0) return cmp;
return this.createdAt.compareTo(other.createdAt); // 같은 우선순위면 먼저 온 것
}
}
private final PriorityQueue<Task> taskQueue = new PriorityQueue<>();
public void submit(int priority, Runnable work) {
taskQueue.offer(new Task(priority, Instant.now(), work));
}
public void processNext() {
Task task = taskQueue.poll();
if (task != null) {
task.work.run();
}
}
}
병합 정렬된 스트림
K개의 정렬된 리스트를 병합하는 문제입니다. 크기 K인 최소 힙으로 O(N log K)에 해결할 수 있습니다.
public List<Integer> mergeKSortedLists(List<List<Integer>> lists) {
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0]) // 값 기준
);
// 각 리스트의 첫 번째 요소를 힙에 넣기
for (int i = 0; i < lists.size(); i++) {
if (!lists.get(i).isEmpty()) {
pq.offer(new int[]{lists.get(i).get(0), i, 0}); // {값, 리스트인덱스, 요소인덱스}
}
}
List<Integer> result = new ArrayList<>();
while (!pq.isEmpty()) {
int[] min = pq.poll();
result.add(min[0]);
int listIdx = min[1], elemIdx = min[2];
if (elemIdx + 1 < lists.get(listIdx).size()) {
pq.offer(new int[]{lists.get(listIdx).get(elemIdx + 1), listIdx, elemIdx + 1});
}
}
return result;
}
이 패턴은 여러 DB 파티션의 정렬된 결과를 병합할 때도 동일하게 적용됩니다.
정리
- 우선순위 큐는 "**다음에 처리할 가장 중요한 것 **"을 O(1)에 조회하고 O(log n)에 추출하는 자료구조입니다.
- Dijkstra 알고리즘 은 우선순위 큐로 최단 거리 정점을 효율적으로 선택합니다.
- Java ScheduledThreadPoolExecutor 는 힙 기반 큐로 작업 실행 시각을 관리합니다.
- 타이머 이벤트, 작업 우선순위, K개 정렬 리스트 병합 등 다양한 실무 문제에 적용됩니다.
- Spring의
@Scheduled도 내부적으로 힙 기반 스케줄러를 사용합니다.
댓글 로딩 중...