ダブルエンド優先キュー（DEPQ）

ダブルエンド優先キュー（DEPQ）またはダブルエンドヒープは、優先キューまたはヒープのようなデータ構造として定義されますが、に格納されているキーまたはアイテムの順序に従って、最大値と最小値の両方を効率的に削除できます。構造。優先度または値に関連付けられたDEPQのすべての要素。 DEPQでは、昇順と降順の両方で要素を削除または削除することができます。

操作

両端優先キューは、次の操作で構成されます

isEmpty（）

この関数は、DEPQが空かどうかをチェックし、空の場合はtrueを返します。

size（）

この関数は、DEPQに存在する要素の総数を返す役割を果たします。

getMin（y）

この関数は、優先度が最も低い要素yを返す役割を果たします。

getMax（y）

この関数は、最も優先度の高い要素yを返す役割を果たします。

put（y）

この関数は、要素yをDEPQに挿入する役割を果たします。

removeMin（y）

この関数は、最小の優先度で要素yを削除し、この要素を返す役割を果たします。

removeMax（y）

この関数は、最大の優先度で要素yを削除し、この要素を返す役割を果たします。

実装

両端優先キューは、平衡二分探索木（最小要素と最大要素がそれぞれ左端と右端のリーフとして扱われる）から構築または形成するか、最小-最大ヒープやペアリングヒープなどの特殊なデータ構造を実装できます。

通常の優先キューから両端の優先キューに到達する一般的な方法は次のとおりです。

二重構造法

この方法によれば、最小と最大の2つの異なる優先度キューが設定または維持されます。両方の優先度キューの同じ要素が、対応ポインターを使用して表示または表示されます。

ここで、最小要素と最大要素は、それぞれ最小ヒープと最大ヒープのルートノードに含まれる値として示されます。

最小要素の削除 −最小ヒープでremovemin（）を操作し、最大ヒープでremove（node value）を操作します。ここで、ノード値は、最大ヒープ内の対応するノードの値として定義されます。

最大要素の削除 −最大ヒープでremovemax（）を操作し、最小ヒープでremove（node value）を操作します。ここで、ノード値は最小ヒープ内の対応するノードの値として定義されます。

トータル対応

要素の半分は最小優先度キューにあり、残りの半分は最大優先度キューにあります。最小優先度キューの各要素は、最大優先度キューの要素と1対1で対応しています。 DEPQの要素数が奇数値を示している場合、要素の1つがバッファー、つまり特定のストレージ領域に保持されます。最小優先度キュー内のすべての要素の優先度は、最大優先度キュー内の対応する要素以下になります。

葉の対応

この方法によれば、最小優先度キューと最大優先度キューのリーフ要素のみが、対応する1対1のペアを形成します。非リーフ要素が1対1の対応ペアである必要はありません。

インターバルヒープ

上記の対応方法に加えて、DEPQは完全にインターバルヒープを実装して取得できます。インターバルヒープは、各ノードが2つの要素で構成される埋め込み最小-最大ヒープのようなものです。これは、-

• 左側の要素は常に右側の要素以下です。
• 両方の要素が閉じた間隔を定義または指定します。
• ルート以外のノードによって表される間隔は、親ノードのサブ間隔として示されます。
• 左側の要素は、最小ヒープを定義または示します。
• 右側の要素は、最大ヒープを定義または示します。