DEPQ（両端優先度キュー）の一般的な構築手法：デュアルヒープと対応付け技法を解説

はじめに

両端優先度キュー（DEPQ：Double Ended Priority Queue）は、最小要素と最大要素の両方へ効率的にアクセスできるデータ構造です。単一端の優先度キュー（PQ）のデータ構造のうち、remove(aNode)操作（指定したノードaNodeをPQから削除する操作）を効率的に実装できるものであれば、そこから効率的なDEPQデータ構造を導き出す一般的な手法が存在します。本記事では、その代表的な3つの手法「デュアル構造法」「全対応付け」「葉対応付け」について解説します。

デュアルヒープ（Dual Heap）

これらの手法の中で最も単純なのが「デュアル構造法（dual structure method）」です。この手法では、DEPQの全要素について最小ヒープ（min PQ）と最大ヒープ（max PQ）の両方を管理し、同じ要素に対応する最小ヒープのノードと最大ヒープのノードの間に、対応ポインタ（correspondence pointers）を設定します。

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

図A：デュアルヒープ

図では各要素が最小ヒープと最大ヒープの両方に格納されているように見えますが、実際には各要素を2つのヒープのどちらか一方にのみ格納すれば十分です。

isEmpty操作やsize操作は、DEPQ内の要素数を記録する変数sizeを管理することで実現できます。最小要素は最小ヒープの根（ルート）に、最大要素は最大ヒープの根に位置します。要素Aを挿入する際は、Aを最小ヒープと最大ヒープの両方に挿入し、その後、両ヒープにおけるAの位置の間に対応ポインタを設定します。最小要素を削除する場合は、最小ヒープからremoveMinを実行するとともに、最大ヒープからremove(aNode)（aNodeは削除した要素に対応するノード）を実行します。最大要素の削除も同様の手順で行います。

全対応付けと葉対応付け（Total and Leaf Correspondence）

全対応付け（total correspondence）と葉対応付け（leaf correspondence）は、より洗練された対応付けの手法です。いずれの手法でも、要素の半分を最小PQに、残りの半分を最大PQに配置します。要素数が奇数の場合は、1つの要素をバッファに格納します。このバッファ内の要素は、どちらのPQにも所属しません。

全対応付け（Total Correspondence）

全対応付けの手法では、最小PQ内の各要素xが、最大PQの異なる要素yと1対1でペアになります。対応ペア(x, y)は、priority(x) <= priority(y) という関係を満たします。

図Bは、11個の要素3、4、5、5、6、6、7、8、9、10、11からなる全対応付けヒープを示しています。要素10がバッファに格納されており、対応ペアは赤い矢印で表されています。

図B：全対応付けヒープ

葉対応付け（Leaf Correspondence）

葉対応付けの手法では、最小PQと最大PQの各葉（リーフ）要素が必ず対応ペアの一部である必要があります。一方、葉以外の要素は対応ペアに属する必要はありません。図Cは葉対応付けヒープの例です。

図C：葉対応付けヒープ

3つの手法の比較

全対応付けと葉対応付けの構造は、デュアル構造よりも必要なメモリ領域が少なくて済むという利点があります。その一方で、全対応付けおよび葉対応付け構造におけるDEPQアルゴリズムは、デュアル構造のものよりも複雑になります。3つの対応付け手法の中では、葉対応付けが最も高速なDEPQ構造を提供するとされています。

計算量

上述の対応付け手法のいずれかを用いることで、ヒープ、高さバイアス左翼木（height biased leftist tree）、ペアリングヒープ（pairing heap）からDEPQ構造を構築できます。これらのDEPQ構造では、put(x)、removeMin()、removeMax()の各操作にO(log n)の時間がかかります（nはDEPQ内の要素数。ペアリングヒープの場合は償却計算量）。それ以外のDEPQ操作は、すべてO(1)の時間で実行できます。