운영체제의 작업 스케줄링, 다익스트라 최단 경로 알고리즘, 이벤트 드리븐 시뮬레이션... 이 모든 것의 공통점은 우선순위 큐를 사용한다는 것이다. 우선순위 큐는 "가장 중요한 것을 먼저 처리한다"는 단순한 아이디어지만, 효율적인 구현은 생각보다 복잡하다.

한쪽 끝과 양쪽 끝 우선순위 큐

우선순위 큐(priority queue) 는 각 원소가 연관된 우선순위를 갖고 있는 원소들의 모임이다. 가령 시스템의 작업 우선도를 설정해 줄 때에는 작업들을 우선 순위에 따라 분류해야 하며, 2개의 서버로 이루어진 시스템의 경우에 하나의 시스템이 사고로 인해 종료되는 경우 반대쪽 서버로 그 작업 내역들이 병합되어야 하는데 이러한 경우 우선순위 큐를 통해 두 작업 리스트를 병합해야 한다.

이러한 우선순위 큐 한쪽 끝 우선순위 큐 와 양쪽 끝 우선순위 큐 가 있으며, 한쪽 끝 우선순위 큐는 최대 우선순위 큐 와 최소 우선순위 큐 로 나뉜다.

최소 우선순위 큐 에 의해 지원되는 연산은 다음과 같다. SP1. 최소 우선순위를 가진 원소의 반환 SP2. 임의 우선순위를 가진 원소의 삽입 SP3. 최소 우선순위를 가진 원소의 삭제

이러한 우선순위 큐를 잘 표현하기 위한 고전적인 자료 구조로써 히프(heap) 를 사용한다.

양쪽 끝 우선순위 큐는 최소 우선순위 큐와 최대 우선순위 큐가 하나로 합해진 최소-최대 우선순위 큐이다.

실제 활용도 측면에서, 양쪽 끝 우선순위 큐는 네트워크 버퍼를 구현하는 데 사용되는데 네트워크 링크를 통해 전송되기를 원하는 패킷들을 가지고 있는 경우 가장 높은 우선순위를 가진 패킷이 전송되고 삭제 되는 최대 삭제 가 행해지는 반면, 네트워크 내의 다른 곳으로 부터 새로운 패킷이 도착하였는데 버퍼가 가득 차 있다면 우선 순위가 가장 낮은 패킷을 지우는 최소 삭제 가 일어나게 된다. 이처럼 작업 큐의 양쪽에서 삽입과 삭제가 가능한 큐를 양쪽 끝 우선순위 큐라고 부른다.

좌향 트리

좌향트리는 합병성 우선순위 큐의 효율적 구현을 제공한다. 좌향 트리의 종류에는 HBLT(Height Biased Leftist Tree)와 WBLT(Weight Biased Leftist Tree)가 있는데, 일반적으로 HBLT를 좌향트리하고 부른다.

이항히프(B-Heap)

좌향 트리에서 지원되는 것과 같은 기능을 수행한다. 개별적인 연산을 수행하는 데 걸리는 시간보다 우선순위 큐의 순차를 수행하는데 걸리는 시점에 관심이 있다. 이항 히프란 최소 트리의 집합이며, 최소 트리 가운데 최소값을 갖는 트리를 가리키는 하나의 포인터가 가리키게 된다.

---

마무리

우선순위 큐의 핵심 포인트를 정리하면:

구현 방식	삽입	삭제(최소/최대)	병합
정렬된 배열	O(n)	O(1)	O(n)
정렬 안 된 배열	O(1)	O(n)	O(1)
히프	O(log n)	O(log n)	O(n)
좌향 트리	O(log n)	O(log n)	O(log n)

개인적인 생각: 실무에서 우선순위 큐를 직접 구현할 일은 거의 없다. 대부분의 언어가 heapq(Python), PriorityQueue(Java) 같은 내장 라이브러리를 제공한다. 하지만 히프의 동작 원리를 이해하면, "왜 삽입이 O(log n)인지", "왜 힙 정렬이 O(n log n)인지"를 이해할 수 있다.

코딩 테스트에서는 다익스트라 알고리즘 구현할 때 우선순위 큐를 자주 쓴다. Python의 heapq는 최소 히프만 지원하므로, 최대 히프가 필요하면 값에 -1을 곱해서 넣는 트릭을 쓴다.