ソフトヒープ

コンピュータ サイエンスにおいて、ソフト ヒープは、5 種類の操作に対して一定の償却時間計算量を持つ単純なヒープ データ構造のバリエーションです。これは、ヒープ内の最大で一定数の値のキーを慎重に「破壊」 (増加) することで実現されます。

定数時間演算は以下の通りである: ^{[1] [2]}

• create ( S ): 新しいソフトヒープを作成する
• insert ( S , x ): ソフトヒープに要素を挿入する
• meld ( S , S' ): 2つのソフトヒープの内容を1つに結合し、両方を破棄する
• delete ( S , x ): ソフトヒープから要素を削除する
• findmin ( S ): ソフトヒープ内の最小キーを持つ要素を取得する

フィボナッチ ヒープなどの他のヒープは、これらの境界のほとんどを破損なしで達成しますが、重要な削除操作で定数時間の境界を提供することはできません。破損の量はパラメーター の選択によって制御できますが、これを低く設定するほど、挿入に必要な時間が長くなります。Big -O 記法で表すと、エラー率が の場合の償却時間はになります。^{[1] [2]}ソフト ヒープの一部のバージョンでは、作成、挿入、および結合操作が最悪の場合でも定数時間かかることを許可し、findmin と delete に対してのみ、最悪の場合のパフォーマンスではなく償却時間を実現します。^[3]比較ソートと同様に、これらのアルゴリズムは比較によってのみキーにアクセスします。整数キーに対する算術演算が許可されている場合、 への時間依存性はまたは (ランダム化により)に削減できます。^[4]${\displaystyle \epsilon }$${\displaystyle O(\log 1/\varepsilon )}$${\displaystyle \epsilon }$${\displaystyle \epsilon }$${\displaystyle O(\log \log 1/\varepsilon )}$${\textstyle O({\sqrt {\log \log 1/\varepsilon }})}$

より正確には、ソフト ヒープが提供するエラー保証は次のようになります。各ソフト ヒープは、0 から 1/2 の間で選択されるパラメータ で初期化されます。その後、任意の時点で最大で 個の破損したキーが含まれます。ここで は、これまでに挿入された要素の数です。これは、現在ヒープにあるキーの一定の割合だけが破損していることを保証するものではないことに注意してください。挿入と削除の不運なシーケンスでは、ヒープ内のすべての要素のキーが破損している可能性があります。同様に、findminとdelete を使用してヒープから抽出された要素のシーケンスで、一定の割合だけが破損したキーを持つことを保証するものではありません。不運なシナリオでは、破損した要素だけがヒープから抽出されます。キーが破損している場合、ソフト キーに格納されている値は、最初に指定された値よりも高くなります。破損によってキーの値が減少することはありません。findmin操作は、破損したキーを含む現在格納されているキーの最小値を検索します。^{[1] [2]}${\displaystyle \epsilon }$${\displaystyle \varepsilon \cdot n}$${\displaystyle n}$

ソフト ヒープは2000 年にバーナード チャゼルによって設計されました。この構造の「破損」という用語は、チャゼルがソフト ヒープにおける「相乗り」と呼んだものの結果です。ソフト ヒープの各ノードには、キーのリンク リストと 1 つの共通キーが含まれています。共通キーは、リンク リスト内のキーの値の上限です。キーがリンク リストに追加されると、その値はソフト ヒープの操作で二度と関係がなくなるため、破損したと見なされます。比較されるのは共通キーのみです。これがソフト ヒープを「ソフト」にするもので、そこに入れられた特定の値が破損するかどうかはわかりません。これらの破損の目的は、データの情報エントロピーを効果的に下げ、データ構造がヒープに関する情報理論の障壁を突破できるようにすることです。^[1]

ソフトヒープは、その制限と予測不可能な性質にもかかわらず、決定論的アルゴリズムの設計に役立ちます。たとえば、最小全域木を見つけるためのこれまでで最高の複雑性を達成するために使用されてきました。^[5]ソフトヒープを使用して効率的な解決が簡素化された他の問題には、ヒープ順序付き木、ソートされた行列、および合計セットを含む構造化された値のセットのいくつかのクラスで 番目の最小要素を見つけることが含まれます。^[6]${\displaystyle k}$

もう一つの簡単な例は、一連の数値の中で最小のものを見つける選択アルゴリズムである。^[1]${\displaystyle k}$${\displaystyle n}$

• エラー率 でソフトヒープ を初期化し、挿入されたキーの最大 33% が破損することを許容します。${\displaystyle 1/3}$
• すべての要素をヒープに挿入します。${\displaystyle n}$
• 繰り返し回数: findmin 操作を実行し、返されるキーを削除します。${\displaystyle n/3}$
• 正しいキーが最大となる削除された要素を とします。${\displaystyle L}$
• 指定されたすべての要素を比較し、 より小さいサブセットと より大きいサブセットに分割します。 に等しい要素は、削除された場合は最初のサブセットに配置され、それ以外の場合は 2 番目のサブセットに配置されます。${\displaystyle L}$${\displaystyle L}$${\displaystyle L}$${\displaystyle L}$
• 番目に小さいものを含むサブセット内で同じ選択アルゴリズムを再帰的に呼び出します。${\displaystyle k}$

アルゴリズムの比較ステップの後、2 つのサブセットのうち最初のサブセットには削除されたキーがすべて含まれているため、少なくとも 個の要素が含まれます。削除されなかった要素のうち、最大で個が破損しているため、少なくとも 個が破損していません。これらの破損していない削除されていない要素はすべて 2 番目のサブセットに属している必要があります。なぜなら、それらはソフト ヒープの (破損している可能性のある) 値 以上の値であり、その値は の真の値 より大きいためです。したがって、両方のサブセットには % から 66 % の要素が含まれます。再帰の各レベルで問題のサイズが定数倍減少するため、アルゴリズムの合計時間は等比級数で制限され、 であることが示されます。^[1]${\displaystyle n/3}$${\displaystyle 2n/3}$${\displaystyle n/3}$${\displaystyle n/3}$${\displaystyle L}$${\displaystyle L}$${\displaystyle O(n)}$