---

• 결합 가능한 DEPQ(MDEPQ)는 위에 나열된 DEPQ 작업 외에도 meld(p, q) ... DEPQ p 및 q를 다음으로 결합하는 작업을 포함하는 DEPQ(이중 종료 우선 순위 대기열)로 정의됩니다. 단일 DEPQ. 양방향 우선순위 큐 p와 q를 결합한 결과는 p와 q의 모든 요소를 ​​포함하는 단일 양방향 우선순위 큐입니다. 혼합 작업은 혼합 후 p와 q가 독립적인 DEPQ로 유지되지 않는다는 점에서 파괴적입니다.
• 선형 시간보다 짧은 시간에 두 개의 DEPQ를 결합하려면 DEPQ가 명시적 포인터(힙의 배열 표현에서와 같이 암시적 포인터가 아닌)를 구현하여 표현되어야 합니다. 이니셜에서 최종 위치로 이동합니다.
• 최소-최대 쌍 힙이 이와 같이 표현될 때 O에서 요소(n의 크기) DEPQ가 다른 요소(k의 크기)(여기서 k<=n)와 혼합될 수 있음을 알 수 있습니다. (log(n/k)*log k) 시간.
• 각각 크기가 a와 b인 두 개의 최소-최대 힙을 합칠 때의 복잡도는 Ω(a + b)임을 알 수 있습니다.
• 최소 및 최대 요소를 계산하고, 요소를 삽입하고, O(1) 시간에 두 개의 우선 순위 대기열을 결합할 수 있는 MDEPQ 구현입니다. 최소 또는 최대 요소를 삭제하는 데 필요한 시간은 O(log n)입니다.
• 좌파 트리는 혼합이 대수 시간을 소비하고 나머지 작업이 앞서 언급한 DEPQ 표현이 구현될 때와 동일한 점근적 복잡성을 갖는 MDEPQ에 대한 간단한 표현을 얻도록 조정될 수 있음을 보여줄 수 있습니다.
• FMPQ(Fast Meldable Priority Queue) 구조를 기본 MPQ 구조로 구현하면 removeMax 및 removeMin이 대수 시간을 소비하고 나머지 작업이 상수를 소비하는 전체 대응 MDEPQ 구조를 얻을 수 있다는 점에 유의하십시오. 시각. 이 적응은 공간 요구 사항이 거의 절반이기 때문에 이중 우선 순위 대기열 적응과 비교할 때 우수합니다. 또한 전체 통신 적응이 이중 우선 순위 대기열 적응보다 빠릅니다.