マージ可能DEPQ（MDEPQ）とは？定義・計算量・実装手法を徹底解説

マージ可能DEPQ（MDEPQ）の定義

マージ可能DEPQ（Meldable DEPQ、MDEPQ）とは、通常の両端優先度付きキュー（Double Ended Priority Queue、DEPQ）が備える基本操作に加えて、meld(p, q) という操作を提供するデータ構造です。この操作は、2つのDEPQである p と q を1つのDEPQへと併合（マージ）します。併合の結果得られるDEPQには、p と q が保持していたすべての要素が含まれます。なお、meld操作は破壊的（destructive）であるため、実行後には p と q が独立したDEPQとして残ることはありません。

線形時間未満でマージするための前提条件

2つのDEPQを線形時間未満でマージするには、データ構造が明示的なポインタ（explicit pointer）によって表現されている必要があります。ヒープを配列で表現する場合のような暗黙的なポインタ（implicit pointer）では、マージ時に線形個の要素を初期位置から最終位置へ移動させる必要が生じるためです。

代表的な実装のマージ計算量

ミンマックスペアヒープの場合

ミンマックスペアヒープ（min-max pair heap）を明示的ポインタで表現した場合、サイズ n のDEPQとサイズ k のDEPQ（k ≤ n）を O(log(n/k) × log k) 時間でマージできることが示されています。

ミンマックスヒープの場合

一方、サイズがそれぞれ a と b である2つのミンマックスヒープ（min-max heap）をマージする計算量は Ω(a + b) であることが知られています。つまり、この構造では高速なマージは実現できません。

定数時間の基本操作を持つMDEPQ実装

特定のMDEPQ実装では、最小要素・最大要素の参照、要素の挿入、そして2つの優先度付きキューのマージを、いずれも O(1) 時間で実行できます。最小要素または最大要素を削除する操作に必要な時間は O(log n) です。

左偏木（Leftist Tree）を用いた実装

左偏木（leftist tree）を応用することで、マージに対数時間で処理できるシンプルなMDEPQ表現を得られることが示されています。この実装では、マージ以外の操作も、前述のいずれかのDEPQ表現を用いた場合と同じ漸近的計算量を維持します。

FMPQを基盤とする全対応MDEPQ

興味深いことに、FMPQ（Fast Meldable Priority Queue）構造をベースのMPQ（Meldable Priority Queue）構造として採用すると、全対応（total correspondence）MDEPQ構造が得られます。この構造では、removeMax と removeMin は対数時間で処理され、その他の操作はすべて定数時間で完了します。

この全対応による実装は、デュアル優先度付きキュー（dual priority queue）を用いた実装と比較して優れています。必要な記憶領域がほぼ半分で済むだけでなく、全対応版の方がデュアル優先度付きキュー版よりも高速に動作するためです。