우선순위 큐 (Priority Queue)

한 줄 정의: 저장된 데이터마다 우선순위를 매겨두고, 넣은 순서와 상관없이 항상 우선순위가 가장 높은(또는 가장 낮은) 항목을 먼저 꺼낼 수 있게 만든 자료구조입니다.

쉽게 풀면

병원 응급실을 생각해 보면 쉽습니다. 접수한 순서대로 진료를 본다면 먼저 온 가벼운 환자가 나중에 온 위급한 환자보다 먼저 치료받게 되어 문제가 생길 수 있습니다. 그래서 응급실은 접수 순서가 아니라 "위급한 정도(우선순위)"에 따라 환자를 부릅니다. 우선순위 큐도 마찬가지로, 데이터를 넣을 때 우선순위 값을 함께 매겨두고, 꺼낼 때는 항상 그중 가장 급한(또는 값이 가장 작은/큰) 데이터부터 내어줍니다. 보통 내부적으로는 힙(heap)이라는 트리 구조를 사용해서, 데이터가 아무리 많아도 최우선 항목을 빠르게 찾아낼 수 있도록 구현합니다.

왜 중요한가

우선순위 큐는 "다음에 무엇을 먼저 처리할지"를 효율적으로 결정해야 하는 거의 모든 알고리즘의 밑바탕이 되기 때문에, 그래프 탐색·인공지능 탐색·시스템 스케줄링 등 폭넓은 분야의 논문에서 등장합니다. 특히 휴리스틱 탐색이나 강화학습처럼 후보 상태에 우선순위(비용, 점수)를 매겨 처리 순서를 정해야 하는 문제에서는 우선순위 큐의 선택이 알고리즘의 실행 속도를 좌우합니다. 이 때문에 새로운 알고리즘을 제안하는 논문에서 우선순위 큐의 구현 방식과 시간복잡도를 명시하는 것이 관행처럼 자리 잡았습니다.

논문에서는 이렇게 쓰입니다

"본 연구에서는 다익스트라 알고리즘의 탐색 효율을 높이기 위해 최소 힙 기반 우선순위 큐를 적용하여 전체 시간복잡도를 O(E log V)로 낮추었다."

이 문장은 최단 경로 탐색이나 작업 스케줄링을 다루는 알고리즘 논문의 방법론 부분에서 흔히 등장합니다. 매번 남은 데이터 전체를 훑어 가장 우선순위가 높은 항목을 찾는 대신, 우선순위 큐를 사용하면 탐색 속도를 크게 줄일 수 있다는 점을 강조할 때 인용됩니다.

"A* 탐색 알고리즘에서 각 노드의 예상 비용을 우선순위로 하는 우선순위 큐를 사용하여 목표 지점까지의 경로를 효율적으로 탐색하였다."

인공지능 및 로보틱스 경로계획 연구에서는 우선순위 큐가 휴리스틱 함수 값을 기준으로 다음에 탐색할 노드를 선택하는 데 사용된다.

"분산 작업 큐 시스템에서 사용자 등급에 따라 요청의 우선순위를 부여하고, 우선순위 큐를 통해 처리 순서를 동적으로 조정하였다."

시스템 및 클라우드 컴퓨팅 연구에서는 우선순위 큐가 자원 할당이나 요청 처리 순서를 결정하는 스케줄링 메커니즘으로 활용된다.

조금 더 깊게 보면

우선순위 큐는 추상적인 인터페이스(삽입, 최우선 항목 조회 및 제거)를 정의할 뿐, 내부 구현은 힙 외에도 균형 이진탐색트리, 정렬된 배열 등 다양한 방식이 가능합니다. 어떤 구현을 쓰느냐에 따라 삽입·삭제·우선순위 변경 연산의 시간복잡도가 달라지므로, 알고리즘 논문에서는 이 선택이 전체 성능에 미치는 영향을 함께 분석하는 경우가 많습니다. 동일 우선순위 항목이 여러 개일 때의 처리 순서(안정성 여부)도 실제 구현에서 주의 깊게 다뤄야 하는 세부 사항입니다.

주의할 점

우선순위 큐는 스택과 큐처럼 먼저 넣은 순서대로 꺼내주지 않습니다. 오직 우선순위만을 기준으로 다음 항목을 결정하므로, 같은 우선순위를 가진 데이터가 여러 개일 때 어떤 것이 먼저 나올지는 구현 방식에 따라 달라질 수 있어 순서 보장이 필요한 경우 별도로 처리해야 합니다.