CS학습2026년 8월 18일

우선순위 큐(Priority Queue): 중요도에 따라 데이터를 꺼내는 큐

우선순위 큐는 큐와 유사하지만, 각 요소에 우선순위가 부여되어 우선순위가 높은 요소가 먼저 처리됩니다. 힙(Heap) 자료구조를 이용하여 구현하는 경우가 많으며, 최적화 문제, 이벤트 스케줄링, 그래프 탐색 등 다양한 분야에서 활용됩니다. 데이터의 중요도를 고려해야 하는 상황에서 효과적인 자료구조입니다.

송민성3분 읽기

1. 개념

우선순위 큐(Priority Queue)는 추상 데이터 타입(Abstract Data Type, ADT)의 일종으로, 큐(Queue)와 유사하게 FIFO(First-In, First-Out) 방식으로 동작하지만, 각 요소에 우선순위가 부여됩니다. 일반적인 큐는 데이터를 삽입한 순서대로 꺼내지만, 우선순위 큐는 우선순위가 가장 높은 요소(가장 '중요한' 데이터)를 먼저 꺼냅니다.

2. 왜 사용하는가

우선순위 큐는 다음과 같은 상황에서 유용합니다.

최적화 문제: 가장 비용이 적은 경로를 찾는 다익스트라(Dijkstra) 알고리즘, 최소 신장 트리(Minimum Spanning Tree)를 찾는 프림(Prim) 알고리즘 등
스케줄링: 운영체제에서 프로세스 스케줄링, 작업 스케줄링 등
이벤트 처리: 이벤트 발생 시간을 기준으로 이벤트 처리 순서를 결정
데이터 스트림 처리: 실시간 데이터 스트림에서 가장 중요한 데이터 추출

3. 동작 원리

우선순위 큐는 일반적으로 힙(Heap) 자료구조를 사용하여 구현됩니다. 힙은 완전 이진 트리(Complete Binary Tree) 기반의 자료구조로, 다음과 같은 특징을 가집니다.

최대 힙(Max Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같습니다. (가장 큰 값이 루트 노드에 위치)
최소 힙(Min Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같습니다. (가장 작은 값이 루트 노드에 위치)

우선순위 큐는 최소 힙 또는 최대 힙을 사용하여 구현할 수 있으며, 일반적으로 최소 힙을 사용하여 구현하는 경우가 많습니다.

삽입(Insert): 새로운 요소를 힙의 가장 마지막 노드에 삽입한 후, 부모 노드와 비교하여 우선순위가 높으면 교환하는 과정을 반복합니다. (Up-heap 또는 Bubble-up)
삭제(Delete): 루트 노드(최고 우선순위 요소)를 삭제하고, 가장 마지막 노드를 루트 노드로 이동시킨 후, 자식 노드와 비교하여 우선순위가 높으면 교환하는 과정을 반복합니다. (Down-heap 또는 Bubble-down)

4. 코드 예제

python

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0  # 동점자 처리를 위한 인덱스

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item)) # priority는 음수로 저장하여 최소힙으로 동작하도록 함
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

    def is_empty(self):
        return len(self._queue) == 0

5. 시간 복잡도 또는 성능 특성

삽입(Insert): O(log n) - 힙의 높이에 비례
삭제(Delete): O(log n) - 힙의 높이에 비례
peek(최고 우선순위 요소 확인): O(1) - 루트 노드 접근
공간 복잡도: O(n) - 힙에 저장되는 요소의 개수에 비례

6. 실무 사용 사례

웹 서버 요청 처리: 높은 우선순위의 요청을 먼저 처리하여 사용자 경험 개선
네트워크 패킷 스케줄링: QoS(Quality of Service) 보장을 위해 중요한 패킷을 우선적으로 전송
게임 AI: 적 캐릭터의 행동 결정 시, 위협도가 높은 행동을 우선적으로 선택

7. 주의할 점

우선순위 큐는 정렬된 자료구조가 아닙니다. 특정 우선순위의 요소들을 찾기 위해서는 별도의 탐색 과정이 필요합니다.
힙 자료구조는 메모리 사용량이 비교적 높을 수 있습니다.
동일한 우선순위를 가진 요소가 많을 경우, 삽입/삭제 성능이 저하될 수 있습니다. (위의 Python 코드에서는 _index를 사용하여 동점자 처리를 함)

8. 핵심 정리

우선순위 큐는 요소의 중요도를 고려하여 데이터를 처리해야 하는 상황에서 유용합니다. 힙 자료구조를 이용하여 구현하며, 삽입 및 삭제 연산의 시간 복잡도는 O(log n)입니다. 다양한 실무 분야에서 활용될 수 있으며, 성능과 메모리 사용량을 고려하여 적절히 사용해야 합니다.