ダブルエンド優先キュー（DEPQ）とは？基本操作と実装方法を徹底解説

ダブルエンド優先キュー（Double-Ended Priority Queue：DEPQ）、別名「両端ヒープ」は、通常の優先キュー（ヒープ）とよく似たデータ構造ですが、最大の特徴は、格納されたキーや要素の順序付けに基づいて最大値と最小値の両方を効率的に取り出せる点にあります。

DEPQ内のすべての要素には、優先度または値が関連付けられており、要素を昇順・降順のどちらの方向にも取り出したり削除したりすることが可能です。

DEPQの基本操作

ダブルエンド優先キューは、以下の操作で構成されます。

isEmpty()

DEPQが空かどうかを確認する関数です。キューが空であれば true を返します。

size()

DEPQに現在格納されている要素の総数を返す関数です。

getMin(y)

最も優先度が低い要素 y を取得して返す関数です。

getMax(y)

最も優先度が高い要素 y を取得して返す関数です。

put(y)

新しい要素 y をDEPQに挿入する関数です。

removeMin(y)

最小の優先度を持つ要素 y を削除し、その要素を返す関数です。

removeMax(y)

最大の優先度を持つ要素 y を削除し、その要素を返す関数です。

実装方法

両端優先キューは、平衡二分探索木から構築できます。この場合、最小要素と最大要素はそれぞれ木の左端と右端の葉として扱われます。また、ミンマックスヒープやペアリングヒープといった特殊なデータ構造を実装することでも構築可能です。

さらに、通常の優先キューから両端優先キューを導出するための汎用的な手法として、以下の方式が知られています。

デュアル構造方式（Dual Structure Method）

この方式では、min（最小値）用とmax（最大値）用に2つの独立した優先キューを保持します。両方の優先キューに存在する同一要素は、「対応ポインタ」によって相互に関連付けられます。

このとき、最小要素と最大要素は、それぞれミンヒープとマックスヒープの根ノード（ルートノード）に格納された値として表されます。

• 最小要素の削除： ミンヒープに対して removemin() を実行し、同時にマックスヒープに対して remove(node value) を実行します。ここでの node value とは、マックスヒープ内の対応するノードに格納された値を指します。
• 最大要素の削除： マックスヒープに対して removemax() を実行し、同時にミンヒープに対して remove(node value) を実行します。ここでの node value とは、ミンヒープ内の対応するノードに格納された値を指します。

全対応方式（Total Correspondence）

この方式では、要素の半分をmin優先キューに、残りの半分をmax優先キューに振り分けます。min優先キュー内の各要素は、max優先キュー内の要素と一対一で対応します。

DEPQ全体の要素数が奇数の場合、余った1つの要素は「バッファ」と呼ばれる専用の記憶領域に保持されます。また、min優先キュー内の各要素の優先度は、必ず対応するmax優先キュー内の要素の優先度以下になるように管理されます。

葉対応方式（Leaf Correspondence）

この方式では、min優先キューとmax優先キューにおける葉要素のみが一対一の対応ペアを形成します。非葉（内部）要素については、一対一の対応関係を保つ必要はありません。これにより、全対応方式よりも柔軟な構造管理が可能になります。

インターバルヒープ（Interval Heap）

上述の対応方式に加えて、インターバルヒープを用いることでもDEPQを効率的に構築できます。インターバルヒープは、各ノードが2つの要素で構成される埋め込み型のミンマックスヒープであり、以下の性質を持つ完全二分木として定義されます。

• 左側の要素は、常に右側の要素以下である。
• 左右の2つの要素が、ひとつの閉区間を定義する。
• 根以外の任意のノードが表す区間は、必ず親ノードの区間の部分区間となる。
• 左側に並ぶ要素群は、ミンヒープを構成する。
• 右側に並ぶ要素群は、マックスヒープを構成する。

このような構造により、インターバルヒープは単一の木で最小値と最大値の双方への高速アクセスを実現しており、DEPQの実装手段として非常に有用です。