対応ベースのデータ構造とは？全体対応と葉対応の仕組みを徹底解説

対応ベースのデータ構造の概要

全体対応（Total Correspondence）と葉対応（Leaf Correspondence）は、より洗練された対応手法として知られています。いずれの手法においても、要素の半分は最小優先度キュー（min PQ）に、残りの半分は最大優先度キュー（max PQ）に配置されます。

また、要素の総数が奇数である場合には、1つの要素がバッファに格納されます。このバッファに置かれた要素は、どちらの優先度キューにも所属しない点が特徴です。

全体対応（Total Correspondence）の仕組み

全体対応の手法では、最小優先度キュー内の各要素 x が、最大優先度キュー内の別の要素 y と一対一でペアになります。このとき、(x, y) は対応する要素のペアであり、priority(x) <= priority(y) という関係が常に成り立つように管理されます。

下の図Eは、3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11 の11個の要素から構成される全体対応ヒープの例です。この例では要素 10 がバッファに格納されており、対応するペア同士は赤い矢印で結ばれて示されています。

図E：全体対応ヒープ

葉対応（Leaf Correspondence）の仕組み

葉対応の手法では、最小優先度キューおよび最大優先度キューにおけるすべての葉（リーフ）要素が、必ず対応ペアの一部となる必要があります。一方で、葉以外の内部ノードについては、どの対応ペアにも属する義務はありません。下の図Fは、葉対応ヒープの一例を示したものです。

図F：葉対応ヒープ

空間効率と処理速度の比較

全体対応および葉対応の構造は、デュアル構造（dual structures）と比べて必要な記憶領域を抑えられるという利点があります。その一方で、これらの構造に対する両端優先度キュー（DEPQ）のアルゴリズムは、デュアル構造向けのものよりも複雑になる傾向があります。

3つの対応手法を処理速度の観点から比較すると、葉対応が最も高速なDEPQ対応構造であることが知られています。実装の容易さと性能のバランスを考慮し、用途に応じて最適な手法を選択することが重要です。