DEPQ(Double Ended Priority Queue, 양방향 우선순위 큐)는 우선순위 큐나 힙과 유사한 자료구조이지만, 저장된 키(key)나 항목의 정렬 기준에 따라 최댓값과 최솟값을 모두 효율적으로 삭제할 수 있다는 점이 특징입니다. DEPQ의 모든 요소는 각각 고유한 우선순위(priority) 또는 값을 가지며, 이를 통해 오름차순과 내림차순 두 방향 모두로 요소를 제거할 수 있습니다.
DEPQ의 주요 연산
양방향 우선순위 큐는 다음과 같은 핵심 연산을 제공합니다.
isEmpty()
DEPQ가 비어 있는지 검사하는 함수입니다. 큐가 비어 있으면 true를 반환합니다.
size()
DEPQ에 현재 저장된 요소의 총 개수를 반환합니다.
getMin()
우선순위가 가장 낮은 요소를 조회하여 반환합니다. 실제 삭제는 이루어지지 않습니다.
getMax()
우선순위가 가장 높은 요소를 조회하여 반환합니다.
put(y)
새로운 요소 y를 DEPQ에 삽입합니다.
removeMin()
최소 우선순위를 가진 요소를 제거하고 해당 요소를 반환합니다.
removeMax()
최대 우선순위를 가진 요소를 제거하고 해당 요소를 반환합니다.
DEPQ 구현 방법
양방향 우선순위 큐는 균형 이진 탐색 트리(Balanced BST)를 기반으로 구축할 수 있습니다. 이 경우 최솟값은 가장 왼쪽 리프 노드에서, 최댓값은 가장 오른쪽 리프 노드에서 찾을 수 있습니다. 또는 min-max 힙(min-max heap), 페어링 힙(pairing heap)과 같은 특수 목적 자료구조를 활용해 구현하기도 합니다.
일반적인 우선순위 큐로부터 양방향 우선순위 큐를 만드는 대표적인 방법은 다음과 같습니다.
1. 이중 구조 방법(Dual Structure Method)
이 방식에서는 최소 힙과 최대 힙 두 개의 우선순위 큐를 동시에 유지합니다. 두 큐에 동일하게 존재하는 요소들은 대응 포인터(correspondence pointer)로 서로 연결됩니다.
- 최솟값과 최댓값은 각각 min 힙과 max 힙의 루트 노드에 저장된 값으로 표현됩니다.
- 최솟값 제거: min 힙에서 removeMin()을 수행하고, max 힙에서는 대응 노드의 값을 기준으로 remove()를 수행합니다.
- 최댓값 제거: max 힙에서 removeMax()를 수행하고, min 힙에서는 대응 노드의 값을 기준으로 remove()를 수행합니다.
2. 전체 대응 방법(Total Correspondence)
전체 대응 방식에서는 절반의 요소는 min 우선순위 큐에, 나머지 절반은 max 우선순위 큐에 분배합니다. min 큐의 각 요소는 max 큐의 요소와 일대일(one-to-one)로 대응되며, min 큐에 있는 요소의 우선순위는 항상 대응되는 max 큐 요소의 우선순위보다 작거나 같습니다.
만약 DEPQ에 저장된 요소의 개수가 홀수라면, 하나의 요소는 별도의 임시 저장 공간(buffer)에 보관됩니다.
3. 리프 대응 방법(Leaf Correspondence)
리프 대응 방식에서는 min 힙과 max 힙의 리프(leaf) 요소들만 일대일로 대응됩니다. 비리프(non-leaf) 노드, 즉 내부 노드들은 서로 대응 관계를 유지할 필요가 없습니다.
인터벌 힙(Interval Heap)
앞서 소개한 대응 방법들 외에도, 인터벌 힙(interval heap)을 사용하면 DEPQ를 매우 효율적으로 구현할 수 있습니다. 인터벌 힙은 각 노드가 두 개의 요소를 담고 있는 임베디드(embedded) min-max 힙 형태의 자료구조로, 다음 조건을 만족하는 완전 이진 트리(complete binary tree)입니다.
- 각 노드에서 왼쪽 요소는 항상 오른쪽 요소보다 작거나 같습니다.
- 두 요소는 하나의 폐구간(closed interval)을 정의합니다.
- 루트를 제외한 모든 노드가 나타내는 구간은 부모 노드 구간의 하위 구간(sub-interval)입니다.
- 왼쪽 요소들을 모으면 min 힙 구조를 이룹니다.
- 오른쪽 요소들을 모으면 max 힙 구조를 이룹니다.
이러한 특성 덕분에 인터벌 힙은 단일 트리 구조만으로 최솟값과 최댓값 양쪽에 대한 접근과 삭제를 효율적으로 처리할 수 있어, DEPQ 구현에 널리 활용됩니다.