プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

インターバルヒープの初期化

インターバルヒープは、各ノードに2つの要素が含まれる埋め込み最小-最大ヒープと同じです。これは、完全な二分木として定義されています

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

要素の数に応じて、2つのケースが許可されます-

  • 偶数の要素：この場合、各ノードには、a≤bの2つの要素aとbが含まれます。すべてのノードは、間隔[a、b]で表されます。
  • 奇数の要素：この場合、最後以外の各ノードには、間隔[a、b]で表される2つの要素が含まれますが、最後のノードには1つの要素が含まれ、間隔[a、b]で表されます。 。

インターバルヒープは、通常のヒープを初期化するために使用されるのと同じ戦略を実装して初期化できます。ヒープの下部からルートに向かって作業し、各サブツリーがインターバルヒープとして示されるようにします。サブツリーごとに、最初にルート内の要素を並べ替えます。次に、removeMin関数に使用される再挿入戦略を実装するこのサブツリーのルートの左端点を再度挿入し、次に、removeMax関数に使用される戦略を実装するこのサブツリーのルートの右端点を再度挿入します。


  1. 最小-最大ヒープ

    min-maxヒープは、最小（または偶数）レベルと最大（または奇数）レベルが交互に含まれる完全なバイナリツリーとして定義されます。偶数レベルは、たとえば0、2、4などとして示され、奇数レベルは1、3、5などとして示されます。 次のポイントでは、ルート要素が最初のレベル、つまり0にあると見なします。 最小-最大ヒープの例 最小-最大ヒープの機能 最小最大ヒープ内の各ノードは、最小最大ヒープ内のノードの順序を計算するために値が実装されているデータメンバー（通常はキーと呼ばれます）に関連付けられています。 ルート要素は、最小-最大ヒープの最小要素です。 2番目のレベルの2つの要素の1つ

  2. ペアリングヒープ

    ペアリングヒープは、実装が比較的簡単で、実用的な償却パフォーマンスが優れているヒープデータ構造の一種として定義されています。 ペアリングヒープは、ヒープ順に並べられたマルチウェイツリー構造であり、簡略化されたフィボナッチヒープとして表すことができます。 これらは、プリムのMSTアルゴリズムなどのアルゴリズムを実装するための「堅牢な選択」と見なされ、次の操作をサポートします（最小ヒープを想定）- find-min −この関数は、ヒープの最上位要素を返す役割を果たします。 溶ける -この関数は、2つのルート要素を比較する役割を果たします。結果のルートが小さいほど、大きい要素とそのサブツ