이중 우선순위 큐(DEPQ)란?
이중 우선순위 큐(Double Ended Priority Queue, DEPQ)는 최솟값과 최댓값을 모두 효율적으로 조회하고 삭제할 수 있는 자료구조입니다. 일반적인 단일 방향 우선순위 큐(PQ)는 최솟값 또는 최댓값 중 한쪽만 효율적으로 다룰 수 있지만, DEPQ는 양방향 연산을 지원합니다.
단일 방향 우선순위 큐를 기반으로 효율적인 DEPQ 자료구조를 만드는 일반적인 방법들이 존재합니다. 단, 이때 사용되는 PQ는 remove(bNode) 연산도 효율적으로 제공해야 합니다. remove(bNode)는 우선순위 큐에서 특정 노드 bNode를 제거하는 연산입니다.
쌍대 구조 방식(Dual Structure Method)
이러한 방법 중 가장 간단한 것이 바로 쌍대 구조(dual structure) 방식입니다. 이 방식은 DEPQ의 모든 원소에 대해 최소 힙(min heap)과 최대 힙(max heap)을 동시에 유지하며, 두 힙에서 서로 같은 원소를 저장하고 있는 노드들 사이에 대응 포인터(correspondence pointer)를 설정합니다.
아래 그림 D는 원소 7, 8, 3, 6, 5로 구성된 쌍대 힙 구조를 보여줍니다. 대응 포인터는 빨간색 화살표로 표시되어 있습니다.
그림 D: 쌍대 힙
그림에서는 각 원소가 최소 힙과 최대 힙 양쪽에 모두 저장된 것처럼 보이지만, 실제 구현에서는 각 원소를 두 힙 중 하나에만 저장해도 충분합니다.
주요 연산 살펴보기
isEmpty와 size
isEmpty와 size 연산은 DEPQ에 저장된 원소의 개수를 추적하는 size 변수를 통해 간단히 구현됩니다. 최솟값은 항상 최소 힙의 루트에 위치하고, 최댓값은 최대 힙의 루트에 위치하므로 두 값 모두 O(1) 시간에 확인할 수 있습니다.
삽입(Insert)
새로운 원소 B를 삽입할 때는 다음 순서로 진행합니다.
1. B를 최소 힙과 최대 힙 양쪽에 각각 삽입합니다.
2. 두 힙에서 B가 위치한 노드 사이에 대응 포인터를 설정합니다.
삭제(RemoveMin / RemoveMax)
최솟값을 삭제할 때는 최소 힙에서 removeMin 연산을 수행하고, 동시에 최대 힙에서는 삭제된 원소에 대응하는 노드 bNode를 대상으로 remove(bNode) 연산을 수행합니다. 최댓값을 삭제할 때도 이와 유사한 방식으로, 최대 힙에서 removeMax를 수행한 뒤 최소 힙에서 대응 노드를 제거하면 됩니다.
이처럼 쌍대 구조 방식은 두 개의 힙과 대응 포인터만으로 최솟값과 최댓값 연산을 모두 효율적으로 처리할 수 있는 직관적이고 강력한 DEPQ 구현 전략입니다.