データ構造のフィボナッチヒープ
二項ヒープと同様に、フィボナッチヒープは木のコレクションです。それらは大まかに二項ヒープに基づいています。二項ヒープ内のツリーとは異なり、フィボナッチヒープ内のツリーはルート化されていますが、順序付けされていません。
フィボナッチヒープの各ノードxには、その親へのポインターp [x]と、その子のいずれかへのポインターchild[x]が含まれています。 xの子は、xの子リストと呼ばれる循環二重リンクリストでリンクされます。子リスト内の各子yには、それぞれyの左と右の兄弟を指すポインターleft[y]とright[y]があります。ノードyが一人っ子の場合、left [y] =right [y]=yです。兄弟が子リストに表示される順序は任意です。
このフィボナッチヒープHは、5つのフィボナッチヒープと16のノードで構成されています。矢印の付いた線はルートリストを示しています。リスト内の最小ノードは、4を保持しているmin[H]で示されます。
最小スパニングツリーの計算、最短パスの単一ソースの検索などの問題に対する漸近的に高速なアルゴリズムは、フィボナッチヒープを本質的に利用します。
-
データ構造のインターバルヒープ
ここでは、間隔ヒープとは何かを確認します。間隔ヒープは完全な二分木であり、最後のノードを除く各ノードには2つの要素が含まれている可能性があります。ノードPの2つの要素の優先順位を「a」と「b」とします。ここでは、≤bを検討しています。ノードPは閉区間[a、b]を表すと言います。ここで、aはPの区間の左端であり、bは右端です。 [c、d]は、a≤c≤d≤bの場合に限り、区間[a、b]に含まれます。区間ヒープでは、各ノードPの左右の子で表される区間は、Pで表される区間に含まれます。最後のノードに優先度cの単一要素が含まれている場合、a≤c≤bです。ここで、[a、b]は最後のノードの親の間隔です。
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ