DEPQのジェネリックメソッド

デュアルヒープ

remove（aNode）操作の効率的な実装も提供するシングルエンド優先キュー（PQ）データ構造から効率的なDEPQ（ダブルエンド優先キュー）データ構造に到達するための一般的な方法の存在（この操作はノードaNodeをPQ）。これらの方法の中で最も単純な二重構造法は、同じ要素を構成する最小PQと最大PQのノード間の対応ポインターに関連付けられたすべてのDEPQ要素の最小PQと最大PQの両方を追跡します。

図Aは、要素7、8、3、6、5のデュアルヒープ構造を示しています。対応ポインターは赤い矢印で表示されます。

図A：デュアルヒープ

この図は、最小ヒープと最大ヒープの両方に格納されている各要素を示していますが、各要素は2つのヒープのうちの1つにのみ格納する必要があります。

isEmptyおよびsize操作は、DEPQ内の要素の数を追跡する可変サイズを実装することによって適用されます。最小要素は最小ヒープのルートにあり、最大要素は最大ヒープのルートにあります。要素Aを挿入するには、最小ヒープと最大ヒープの両方にAを挿入してから、最小ヒープと最大ヒープのAの位置の間に対応ポインターを設定します。最小要素を削除するには、最小ヒープからremoveMinを実行し、最大ヒープからremove（aNode）を実行します。ここで、aNodeは削除された要素に対応するノードです。最大要素は同様の方法で削除されます。

合計と葉の対応

トータルとリーフの対応は、より洗練された対応手法です。これらの手法の両方で、要素の半分は最小PQに配置され、残りの半分は最大PQに配置されます。要素数が奇数の場合、1つの要素がバッファに格納されます。このバッファリングされた要素は、どちらのPQのメンバーでもありません。トータルコレスポンデンス手法では、最小PQの各要素xは、最大PQの個別の要素yとペアになります。 （x、y）は、priority（x）<=priority（y）。

図Bは、11個の要素3、4、5、5、6、6、7、8、9、10、11の合計対応ヒープを示しています。要素10はバッファー内にあります。対応するペアは赤い矢印で表示されます。

図B：通信ヒープ全体

リーフ対応手法では、最小および最大PQの各リーフ要素が対応するペアの一部である必要があります。非リーフ要素は、対応するペアである必要はありません。図Cは、リーフ対応ヒープを示しています。

図C：リーフ対応ヒープ

トータルおよびリーフ対応構造は、デュアル構造よりも必要なスペースが少なくて済みます。ただし、合計およびリーフ対応構造のDEPQアルゴリズムは、二重構造のDEPQアルゴリズムよりも複雑です。 3つの対応手法のうち、リーフ対応が最速のDEPQ対応構造です。

説明されている対応手法のいずれかを実装すると、ヒープ、高さバイアスの左辺ツリー、およびペアリングヒープからDEPQ構造に到達できます。これらのDEQP構造では、操作put（x）、removeMin（）、およびremoveMax（）はO（log n）時間を消費します（nはDEPQ内の要素の数であり、ペアリングヒープの場合、これは償却された複雑さです）。残りのDEPQ操作はO（1）時間を消費します。