병합 가능한 DEPQ(MDEPQ)란?
병합 가능한 DEPQ(Meldable DEPQ, MDEPQ)는 기존의 양단 우선순위 큐(Double-Ended Priority Queue, DEPQ) 연산에 더해 meld(p, q) 연산을 추가로 지원하는 자료구조입니다. 이 연산은 두 개의 DEPQ인 p와 q를 하나의 DEPQ로 합치는 기능을 수행합니다. 병합 결과로 생성되는 큐에는 p와 q의 모든 원소가 포함됩니다. 단, meld 연산은 파괴적(destructive)으로 동작하기 때문에 병합이 완료된 후에는 p와 q가 독립적인 DEPQ로 남아 있지 않습니다.
선형 시간 미만의 병합을 위한 조건
두 개의 DEPQ를 선형 시간보다 빠르게 병합하려면, 힙(heap)의 배열 표현에서처럼 암시적 포인터가 아닌 명시적 포인터(explicit pointers)를 사용하여 DEPQ를 구현해야 합니다. 그렇지 않으면 상당수의 원소를 초기 위치에서 최종 위치로 이동시키는 데 선형 개수만큼의 원소 이동 작업이 필요하게 되어 병합 효율이 크게 떨어집니다.
다양한 구조의 병합 복잡도
최소-최대 쌍 힙(min-max pair heap)을 명시적 포인터 방식으로 표현할 경우, 크기가 n인 DEPQ와 크기가 k(k ≤ n)인 다른 DEPQ를 O(log(n/k) × log k) 시간 안에 병합할 수 있다는 것이 증명되어 있습니다.
반면, 각각 크기가 a와 b인 두 개의 최소-최대 힙(min-max heap)을 병합하는 복잡도는 Ω(a + b)임이 알려져 있습니다. 즉, 일반적인 min-max heap 구조는 효율적인 병합 연산에 적합하지 않습니다.
O(1) 병합을 지원하는 MDEPQ 구현
일부 MDEPQ 구현은 최솟값과 최댓값 조회, 원소 삽입, 그리고 두 우선순위 큐의 병합을 모두 O(1) 시간에 수행할 수 있도록 설계되었습니다. 최솟값 또는 최댓값을 삭제하는 데 필요한 시간은 O(log n)입니다.
좌편향 트리(Leftist Tree)를 활용한 구현
좌편향 트리(leftist tree)를 변형하면 병합(meld)에 로그 시간이 소요되고, 나머지 연산들은 앞서 언급한 어떤 DEPQ 표현을 사용하더라도 동일한 점근적 복잗도를 유지하는 간단하고 효율적인 MDEPQ 표현을 얻을 수 있습니다.
FMPQ 기반 총 대응(Total Correspondence) 구조
흥미로운 점은 FMPQ(Fast Meldable Priority Queue) 구조를 기본 MPQ 구조로 활용하면, removeMax와 removeMin 연산은 로그 시간을 소요하고 나머지 연산들은 상수 시간을 소요하는 총 대응(total correspondence) MDEPQ 구조를 얻게 된다는 것입니다. 이 적응 방식은 이중 우선순위 큐(dual priority queue) 적응 방식과 비교했을 때 공간 요구량이 거의 절반에 불과하다는 큰 장점이 있으며, 실행 속도 면에서도 총 대응 방식이 이중 우선순위 큐 방식보다 더 빠릅니다.