シャドウヒープ

コンピュータサイエンスにおいて、シャドウヒープとは、償却的な意味での効率的なヒープマージをサポートするマージ可能なヒープ データ構造です。より具体的には、シャドウヒープはシャドウマージアルゴリズムを利用して、 1 ≤ f( n ) ≤ log log nの任意の値に対して、挿入をO (f(n ) ) 償却時間、削除をO ((log n log log n )/f( n )) 償却時間で実現します。[1]

この記事では、 AとBが | A | ≤ | B |のバイナリ ヒープであると想定します。

シャドウマージ

シャドウマージは、 2つのバイナリヒープが配列として実装されている場合、それらを効率的にマージするアルゴリズムです。具体的には、2つのヒープとにおけるシャドウマージの実行時間は です A {\displaystyle A} B {\displaystyle B} O （ | A | ＋ 分 ｛ ログ ⁡ | B | ログ ⁡ ログ ⁡ | B | , ログ ⁡ | A | ログ ⁡ | B | } ) {\displaystyle O(|A|+\min\{\log |B|\log \log |B|,\log |A|\log |B|\})}

アルゴリズム

2つのバイナリ最小ヒープとをマージします。アルゴリズムは次のとおりです A {\displaystyle A} B {\displaystyle B}

  1. 配列の末尾に配列を連結して配列を取得します。 A {\displaystyle A} B {\displaystyle B} C {\displaystyle C}
  2. 内の のシャドウ、つまりヒープ プロパティを破壊する内の最後のノードの祖先を識別します。 A {\displaystyle A} C {\displaystyle C} | A | {\displaystyle |A|} C {\displaystyle C}
  3. から影の次の 2 つの部分を特定します。 C {\displaystyle C}
    • パス: 任意の 深さで最大 2 個存在する影内のノードのセット。 P {\displaystyle P} C {\displaystyle C}
    • サブツリー: 影の残り部分。 T {\displaystyle T}
  4. 影から最小のノードを抽出し、配列に並べ替えます。 | P | {\displaystyle |P|} S {\displaystyle S}
  5. 次のように変換します。 S {\displaystyle S}
    • の場合、ソートされた配列の最小の要素から始めて、 の各要素を の最小の要素で置き換えて に順番に挿入します。 | S | ＞ | C | {\displaystyle |S|>|C|} S {\displaystyle S} C {\displaystyle C} C {\displaystyle C}
    • の場合、から最小の要素を抽出してソートし、このソートされたリストを とマージします。 | S | ≤ | C | {\displaystyle |S|\leq |C|} | P | {\displaystyle |P|} C {\displaystyle C} S {\displaystyle S}
  6. の要素をの元の位置に置き換えます。 S {\displaystyle S} C {\displaystyle C}
  7. を山盛りにします。 T {\displaystyle T}

実行時間

ここでも、 はパスを表し、 は連結ヒープ のサブツリーを表します。 のノード数はの深さの最大2倍、つまり です。さらに、の深さにおけるノード数は、の深さにおけるノード数の3/4以下であるため、サブツリーのサイズは です。 の各レベルには最大2つのノードがあるため、シャドウの最小要素をソート済み配列に読み込むには時間がかかります。 P {\displaystyle P} T {\displaystyle T} C {\displaystyle C} P {\displaystyle P} C {\displaystyle C} O （ ログ ⁡ | B | ) {\displaystyle O(\log |B|)} T {\displaystyle T} d {\displaystyle d} d ＋ 1 {\displaystyle d+1} O （ | A | ) {\displaystyle O(|A|)} P {\displaystyle P} | P | {\displaystyle |P|} S {\displaystyle S} O （ ログ ⁡ | B | ) {\displaystyle O(\log |B|)}

の場合、上記のステップ5のようにとを結合するのに 時間がかかります。それ以外の場合、このステップにかかる時間は です。最後に、サブツリーのヒープ作成には 時間がかかります。これは、 のシャドウマージにかかる合計実行時間になります。 | S | ＞ | C | {\displaystyle |S|>|C|} P {\displaystyle P} C {\displaystyle C} O （ ログ ⁡ | A | ログ ⁡ | B | ) {\displaystyle O(\log |A|\log |B|)} O （ | A | ＋ ログ ⁡ | B | ログ ⁡ ログ ⁡ | B | ) {\displaystyle O(|A|+\log |B|\log \log |B|)} T {\displaystyle T} O （ | A | ) {\displaystyle O(|A|)} O （ | A | ＋ 分 ｛ ログ ⁡ | A | ログ ⁡ | B | , ログ ⁡ | B | ログ ⁡ ログ ⁡ | B | } ) {\displaystyle O(|A|+\min\{\log |A|\log |B|,\log |B|\log \log |B|\})}

構造

シャドウヒープは、閾値関数と、最初のエントリでは通常の配列実装のバイナリヒープ特性が維持され、他のエントリではヒープ特性が必ずしも維持されない配列で構成されます。したがって、シャドウヒープは本質的に配列に隣接するバイナリヒープです。シャドウヒープに要素を追加するには、配列に配置します。指定された閾値に従って配列が大きくなりすぎた場合は、まずフロイドのヒープ構築アルゴリズム[2]を使用してヒープを構築し、次にシャドウマージを使用してこのヒープをとマージします。最後に、シャドウヒープのマージは、上記の挿入手順を使用して、1つのヒープを別のヒープに順番に挿入することによって行われます H {\displaystyle H} f （ H ) {\displaystyle f(H)} B {\displaystyle B} A {\displaystyle A} A {\displaystyle A} A {\displaystyle A} B {\displaystyle B}

解析

シャドウヒープが与えられ、閾値関数は上記と同じです。閾値関数は、 の変化が の変化よりも大きくならないようなものと仮定します。償却解析のポテンシャル法を用いて、マージ可能なヒープ操作の望ましい実行時間の上界を導出します。ヒープの ポテンシャルは次のように選択されます H ＝ （ B , A ) {\displaystyle H=(B,A)} ログ ⁡ | H | ≤ f （ H ) ≤ ログ ⁡ | H | ログ ⁡ ログ ⁡ | H | {\displaystyle \log |H|\leq f(H)\leq \log |H|\log \log |H|} | B | {\displaystyle |B|} f （ H ) {\displaystyle f(H)} Ψ （ H ) {\displaystyle \Psi (H)}

Ψ （ H ) ＝ | A | （ 1 ＋ 分 ｛ ログ ⁡ | B | ログ ⁡ ログ ⁡ | B | , ログ ⁡ | B | ログ ⁡ | A | } / f （ H ) ) {\displaystyle \Psi (H)=|A|(1+\min\{\log |B|\log \log |B|,\log |B|\log |A|\}/f(H))}

このポテンシャルを使用すると、必要な償却実行時間を取得できます。

create( H ) : 新しい空のシャドウヒープを初期化する H {\displaystyle H}

ここでは、潜在的価値は変わらないので、創造の償却コストは、実際のコストになります。 Ψ {\displaystyle \Psi} O （ 1 ) {\displaystyle O(1)}

insert( x , H ) :シャドウヒープに挿入する × {\displaystyle ×} H {\displaystyle H}

2つのケースがあります:
  • マージが採用された場合、ポテンシャル関数の低下は と のマージの実際のコストとまったく同じなので、償却コストは になります。 B {\displaystyle B} A {\displaystyle A} O （ 1 ) {\displaystyle O(1)}
  • 合併が行われない場合、償却原価は O （ 1 ＋ 分 ｛ ログ ⁡ | B | ログ ⁡ ログ ⁡ | B | , ログ ⁡ | B | ログ ⁡ | A | } / f （ H ) ) {\displaystyle O(1+\min\{\log |B|\log \log |B|,\log |B|\log |A|\}/f(H))}
閾値関数の選択により、挿入の償却コストは次のようになります。
O ( log ⁡ | H | log ⁡ log ⁡ | H | / f ( H ) ) {\displaystyle O(\log |H|\log \log |H|/f(H))}

delete_min( H ) : 最小優先度の要素を削除します。 H {\displaystyle H}

最小値を見つけて削除するには、実際の時間 かかります。さらに、 の値が減少した場合にのみ、この削除後にポテンシャル関数が増加します。 を選択することで、この操作の償却コストは実際のコストと同じになります。 O ( | A | + log ⁡ | B | ) {\displaystyle O(|A|+\log |B|)} f ( H ) {\displaystyle f(H)} f {\displaystyle f}

単純なバイナリヒープマージアルゴリズムは、2つのヒープを単純に連結し、その結果得られた配列からフロイドのヒープ構築アルゴリズムを用いてヒープを作成することで、 2つのヒープをでマージします。あるいは、 の各要素をに順番に挿入することで、 の時間を要してヒープをマージすることもできます。 A {\displaystyle A} B {\displaystyle B} O ( | B | ) {\displaystyle O(|B|)} A {\displaystyle A} B {\displaystyle B} O ( | A | log ⁡ | B | ) {\displaystyle O(|A|\log |B|)}

サックとストロトホッテは、バイナリヒープを時間内にマージするアルゴリズムを提案した。[3]彼らのアルゴリズムは、およそ の場合に、上記の2番目の単純な解決策よりも効率的であることが知られている。シャドウマージは、最悪の場合でも、彼らのアルゴリズムよりも漸近的に優れたパフォーマンスを発揮する。 O ( | A | + log ⁡ | A | log ⁡ | B | ) {\displaystyle O(|A|+\log |A|\log |B|)} | A | > log ⁡ | B | {\displaystyle |A|>\log |B|}

より高速なマージ時間をサポートするヒープは他にもいくつかあります。例えば、フィボナッチヒープは時間内にマージできます。バイナリヒープはマージに時間がかかるため、[4]シャドウマージは依然として効率的です。 O ( 1 ) {\displaystyle O(1)} Ω ( | A | ) {\displaystyle \Omega (|A|)}

参考文献

  1. ^ Kuszmaul, Christopher L. (2000). バイナリヒープとバイナリツリーの効率的なマージおよび挿入操作(PDF) (技術レポート). NASA Advanced Supercomputing Division. 00-003
  2. ^ Suchenek, Marek A. (2012)、「Floydのヒープ構築プログラムの初歩的かつ正確な最悪ケース分析」、Fundamenta Informaticae、120 (1)、IOS Press: 75– 92、doi :10.3233/FI-2012-751
  3. ^ Sack, Jörg-R.; Strothotte, Thomas (1985)、「ヒープのマージのためのアルゴリズム」、Acta Informatica、22 (2)、Springer-Verlag: 171– 186、doi :10.1007/BF00264229、S2CID  6427624。
  4. ^ コーメン、トーマス・H.、レイサーソン、チャールズ・E.、リベスト、ロナルド・L. (1990). 『アルゴリズム入門（第1版）』MITプレス、マグロウヒル. ISBN 0-262-03141-8。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Shadow_heap&oldid=1292670698"