듀얼 힙(Dual Heap)
노드 aNode를 PQ에서 제거하는 remove(aNode) 연산을 효율적으로 지원하는 단일 방향 우선순위 큐(PQ) 자료구조로부터, 효율적인 DEPQ(Double Ended Priority Queue, 양단 우선순위 큐) 자료구조를 만들어 내는 일반적인 방법들이 존재합니다. 이 중 가장 간단한 방법인 듀얼 구조(dual structure) 방식은 DEPQ의 모든 원소에 대해 최소 PQ와 최대 PQ를 모두 유지하고, 동일한 원소를 담고 있는 최소 PQ와 최대 PQ의 노드 사이에 대응 포인터(correspondence pointer)를 설정합니다.
그림 A는 원소 7, 8, 3, 6, 5에 대한 듀얼 힙 구조를 보여줍니다. 대응 포인터는 빨간색 화살표로 표시되어 있습니다.
그림 A: 듀얼 힙
그림에서는 각 원소가 최소 힙과 최대 힙 양쪽에 모두 저장된 것처럼 보이지만, 실제로는 각 원소를 두 힙 중 하나에만 저장하면 됩니다.
isEmpty와 size 연산은 DEPQ에 들어 있는 원소의 개수를 추적하는 size 변수를 통해 구현합니다. 최솟값은 최소 힙의 루트에 위치하고, 최댓값은 최대 힙의 루트에 위치합니다. 원소 A를 삽입할 때는 A를 최소 힙과 최대 힙 양쪽에 삽입한 뒤, 두 힙에서 A가 위치한 곳 사이에 대응 포인터를 설정합니다. 최솟값을 삭제할 때는 최소 힙에서 removeMin을 수행하고, 최대 힙에서는 삭제된 원소에 해당하는 노드 aNode를 인자로 하는 remove(aNode)를 수행합니다. 최댓값 역시 이와 유사한 방식으로 삭제합니다.
전체 대응(Total Correspondence)과 리프 대응(Leaf Correspondence)
전체 대응(total correspondence)과 리프 대응(leaf correspondence)은 더 정교한 대응 기법입니다. 두 기법 모두 원소의 절반은 최소 PQ에, 나머지 절반은 최대 PQ에 저장합니다. 원소의 개수가 홀수인 경우에는 한 개의 원소를 버퍼(buffer)에 보관하며, 이 버퍼의 원소는 어느 쪽 PQ에도 속하지 않습니다. 전체 대응 기법에서는 최소 PQ의 각 원소 x가 최대 PQ의 서로 다른 원소 y와 짝을 이루며, (x, y)는 priority(x) <= priority(y)를 만족하는 대응 쌍입니다.
그림 B는 11개의 원소 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11에 대한 전체 대응 힙을 보여줍니다. 원소 10이 버퍼에 있으며, 대응 쌍은 빨간색 화살표로 표시됩니다.
그림 B: 전체 대응 힙
리프 대응 기법에서는 최소 PQ와 최대 PQ의 각 리프(잎) 원소가 반드시 어떤 대응 쌍에 속해야 합니다. 반면 리프가 아닌 원소들은 대응 쌍에 속할 필요가 없습니다. 그림 C는 리프 대응 힙의 예를 보여줍니다.
그림 C: 리프 대응 힙
전체 대응 및 리프 대응 구조는 듀얼 구조보다 적은 공간을 필요로 합니다. 다만 이들 구조를 위한 DEPQ 알고리즘은 듀얼 구조의 알고리즘보다 복잡합니다. 세 가지 대응 기법 가운데 리프 대응이 가장 빠른 성능을 보이는 DEPQ 대응 구조로 알려져 있습니다.
앞서 설명한 어떤 대응 기법을 사용하더라도, 힙(heap), 높이 편향 좌편향 트리(height biased leftist tree), 페어링 힙(pairing heap)으로부터 DEPQ 구조를 만들어 낼 수 있습니다. 이러한 DEPQ 구조에서 put(x), removeMin(), removeMax() 연산은 O(log n) 시간이 소요되고(n은 DEPQ의 원소 개수이며, 페어링 힙의 경우 분할 상환 복잡도), 나머지 DEPQ 연산들은 O(1) 시간에 수행됩니다.