우선순위 큐와 힙 (Priority Queue & Heap)
쉽게 풀면
병원 응급실을 생각해 보세요. 먼저 온 순서대로 진료하는 것이 아니라, 상태가 위급한 환자부터 먼저 진료합니다. 우선순위 큐가 바로 이런 방식으로 동작하는 자료구조입니다. 데이터를 넣을 때는 순서 상관없이 넣지만, 꺼낼 때는 항상 "우선순위가 가장 높은(혹은 값이 가장 작은/큰)" 원소가 먼저 나옵니다. 이 우선순위 큐를 효율적으로 구현하는 대표적인 방법이 힙(heap)이라는 트리 구조입니다. 힙은 "부모 노드가 항상 자식 노드보다 크거나(혹은 작거나) 같다"는 규칙을 유지해서, 매번 전체를 정렬하지 않고도 가장 중요한 원소를 빠르게 찾아낼 수 있게 해줍니다.
왜 중요한가
우선순위 큐와 힙은 최단 경로, 최소 신장 트리, 스케줄링, 이벤트 시뮬레이션 등 그래프 및 최적화 알고리즘의 시간복잡도를 결정짓는 핵심 구성 요소이기 때문에 알고리즘 논문에서 성능 개선의 근거로 자주 인용됩니다. 힙 기반 구현을 사용하느냐, 피보나치 힙 같은 더 정교한 구조를 사용하느냐에 따라 전체 알고리즘의 이론적 시간복잡도가 달라지므로, 새로운 자료구조나 알고리즘을 제안하는 논문에서는 이 선택 자체가 기여점이 되기도 합니다. 대규모 시스템(네트워크 라우팅, 운영체제 스케줄러 등)에서도 실시간으로 다음 처리 대상을 결정하는 데 필수적으로 쓰입니다.
논문에서는 이렇게 쓰입니다
이 문장은 "여러 후보 노드 중 지금까지 계산된 거리가 가장 짧은 노드를 매번 빠르게 골라내기 위해, 힙 자료구조를 사용했다"는 뜻입니다. 우선순위 큐와 힙은 최단 경로 탐색, 작업 스케줄링, 이벤트 기반 시뮬레이션, 데이터 압축(허프만 코딩) 등에서 핵심적인 역할을 합니다.
실시간 시스템 및 운영체제 연구에서는 우선순위 큐가 마감시간이나 중요도에 따라 작업을 처리하는 스케줄링 알고리즘의 기반으로 쓰인다.
시뮬레이션 및 대규모 네트워크 분석 연구에서는 우선순위 큐가 시간 순서대로 이벤트를 처리하는 이벤트 기반 시뮬레이션 엔진의 핵심 구조로 활용된다.
조금 더 깊게 보면
기본적인 이진 힙(binary heap)은 삽입과 삭제가 로그 시간에 이루어지지만, 우선순위 값을 도중에 낮추는 감소 연산(decrease-key)이 잦은 알고리즘에서는 피보나치 힙(Fibonacci heap)이나 페어링 힙(pairing heap) 같은 더 정교한 구조가 이론적으로 더 나은 성능을 보일 수 있습니다. 다익스트라 알고리즘의 이론적 시간복잡도가 어떤 힙 구현을 쓰느냐에 따라 달라지는 것이 대표적인 예입니다. 실제 구현에서는 이론적 복잡도뿐 아니라 캐시 효율성이나 상수 오버헤드를 고려해 단순 이진 힙이 실용적으로 더 선호되는 경우도 많습니다.
주의할 점
우선순위 큐는 먼저 넣은 것이 먼저 나오는 일반적인 스택과 큐와 이름은 비슷하지만 동작 원리가 다릅니다. 일반 큐는 "선입선출" 순서만 지키지만, 우선순위 큐는 "우선순위" 기준으로 순서가 정해집니다. 또한 힙은 완전히 정렬된 상태를 유지하는 것이 아니라 "가장 중요한 원소를 빠르게 찾을 수 있을 정도로만" 부분적으로 정돈된 구조이므로, 힙 자체를 순서대로 순회해도 전체가 정렬된 목록이 나오지는 않습니다.