우선순위 큐란 무엇인가?
우선순위 큐(Priority Queue)는 일반적인 큐(Queue)나 스택(Stack)과 유사한 추상 자료형(ADT)이지만, 결정적인 차이점이 하나 있습니다. 바로 각 요소에 우선순위(priority)가 부여된다는 점입니다.
일반적인 큐에서는 먼저 들어온 요소가 먼저 처리되는 FIFO(First In, First Out) 방식을 따르지만, 우선순위 큐에서는 우선순위가 높은 요소가 낮은 요소보다 먼저 처리됩니다.
만약 두 요소의 우선순위가 같다면, 일반적인 큐와 마찬가지로 큐에 들어온 순서대로 처리됩니다.
우선순위 큐의 동작 원리 예시
병원 응급실을 생각해 보면 쉽게 이해할 수 있습니다. 환자가 도착한 순서와 상관없이, 응급도가 높은 환자를 먼저 진료하는 것과 같은 원리입니다. 응급도(우선순위)가 같은 환자라면 도착한 순서대로 진료를 받게 됩니다.
우선순위 큐의 구현 방법
우선순위 큐를 구현하는 방법은 다양합니다. 대표적인 구현 방식은 다음과 같습니다.
- 배열(Array): 구현이 간단하지만, 삽입 또는 삭제 시 정렬 비용이 발생할 수 있습니다.
- 힙(Heap): 이진 힙(Binary Heap)을 사용하면 삽입과 삭제 모두 O(log n)의 시간 복잡도를 보장하여 가장 효율적입니다.
- 연결 리스트(Linked List): 정렬된 상태를 유지하며 삽입 위치를 찾아야 하므로 탐색 비용이 듭니다.
이 글에서는 이해하기 쉽도록 배열(Array)을 사용하여 우선순위 큐를 직접 구현해 보겠습니다. 배열 기반 구현은 코드가 단순하고 직관적이어서 학습용으로 적합합니다.
마무리
우선순위 큐는 작업 스케줄링, 다익스트라 최단 경로 알고리즘, 이벤트 시뮬레이션 등 다양한 분야에서 활용되는 핵심 자료구조입니다. 자바스크립트에는 기본적으로 내장된 우선순위 큐가 없기 때문에, 필요에 따라 직접 구현해서 사용해야 합니다. 다음 단계에서 배열 기반 구현 코드를 살펴보겠습니다.