자료구조 큐(Queue)를 배울 때 우리는 '선입선출(FIFO)', 즉 "먼저 온 사람이 먼저 나간다"는 공평한 줄 서기 원칙을 배웠습니다. 하지만 현실 세계가 항상 선착순으로만 돌아갈까요? 어떤 상황에서는 늦게 왔더라도 더 급하고 중요한 일이 먼저 처리되어야 할 때가 있습니다. 이때 필요한 자료구조가 바로 우선순위 큐(Priority Queue)입니다. 일반적인 큐의 규칙을 깨고, 오직 '중요도(Priority)'에 따라 처리 순서를 결정하는 이 스마트한 대기열에 대해 알아보겠습니다.
1. 우선순위 큐란? (응급실의 법칙)
우선순위 큐를 가장 완벽하게 설명하는 예시는 바로 종합병원의 응급실입니다.
- 일반 큐 (은행 창구): 아침 9시에 온 사람이 10시에 온 사람보다 무조건 먼저 업무를 봅니다. (시간 순서)
- 우선순위 큐 (응급실): 감기로 9시에 온 환자가 있더라도, 교통사고로 10시에 실려 온 환자가 있다면 의사는 교통사고 환자를 먼저 치료합니다. 여기서 '시간'은 중요하지 않습니다. '생명의 위급함'이라는 우선순위가 처리 순서를 결정합니다.
컴퓨터 내부에서도 이처럼 들어온 순서와 상관없이, 중요도가 높은 데이터가 먼저 나가는(Out) 자료구조를 우선순위 큐라고 부릅니다.
2. 어떻게 구현하는 것이 가장 효율적일까?
우선순위 큐를 만드는 방법은 여러 가지가 있습니다. 배열이나 연결 리스트로도 만들 수 있습니다. 하지만 왜 대부분 힙(Heap)을 사용하여 구현할까요? 성능(시간 복잡도) 때문입니다.
| 구현 방법 | 데이터 삽입(Enqueue) | 데이터 삭제(Dequeue) |
|---|---|---|
| 배열 (정렬 안 함) | O(1) (그냥 끝에 넣음) | O(n) (가장 큰 거 찾으러 다 뒤져야 함) |
| 배열 (미리 정렬) | O(n) (자리 찾아 끼워 넣고 밀어야 함) | O(1) (맨 끝 꺼내면 됨) |
| 힙 (Heap) | O(log n) | O(log n) |
표에서 볼 수 있듯이, 배열을 사용하면 삽입이나 삭제 중 하나가 O(n)으로 느려집니다. 데이터가 많아지면 치명적입니다. 하지만 힙(Heap)을 사용하면 삽입과 삭제 모두 안정적인 O(log n)의 속도를 보장합니다. 이것이 "우선순위 큐 = 힙"이라는 공식이 생긴 이유입니다.
3. 우선순위 큐의 실제 활용 사례
이 개념은 컴퓨터 과학의 난제들을 해결하는 데 핵심적인 역할을 합니다.
3-1. 다익스트라(Dijkstra) 최단 경로 알고리즘
내비게이션이 길을 찾을 때, 수많은 갈림길 중에서 '현재 가장 거리가 짧은(비용이 적은)' 길부터 먼저 탐색해야 합니다. 이때 거리가 짧은 순서대로 경로를 뱉어주는 우선순위 큐가 사용됩니다.
3-2. 운영체제(OS)의 작업 스케줄링
시스템 내부에는 수많은 프로세스가 돌아갑니다. 그중에서도 시스템 커널 작업이나 실시간 처리가 필요한 작업은 일반 문서 작업보다 우선순위가 높게 설정되어 CPU를 먼저 할당받습니다.
3-3. 데이터 압축 (허프만 코딩)
파일을 압축할 때 문자의 출현 빈도수에 따라 트리를 구성하는데, 이때 빈도수가 가장 낮은 문자를 계속 뽑아내는 과정에서 우선순위 큐가 사용됩니다.
1. 우선순위 큐는 들어온 순서가 아닌 우선순위(중요도)가 높은 데이터가 먼저 나가는 자료구조입니다.
2. 배열보다 힙(Heap)으로 구현하는 것이 삽입/삭제 성능(O(log n)) 면에서 가장 효율적입니다.
3. 응급실 환자 분류, 최단 경로 탐색, 시스템 작업 스케줄링 등 중요도 판단이 필요한 곳에 필수적으로 쓰입니다.