ソフトヒープ

ソフトヒープは、5種類の操作の一定の償却時間で構成される単純なヒープデータ構造のバリエーションとして定義されます。これは、ヒープ内の特定の数の最大値のキーを注意深く「破損」（増加）させることによって取得されます。定数時間演算は-

• 作成 −新しいソフトヒープを作成します
• 挿入（s、y） −要素yをソフトヒープsに挿入します
• meld（s、s'） 2つのソフトヒープsとs'を1つにまとめて、両方を破壊します
• delete（s、y） −ソフトヒープsから要素yを削除します
• findmin（s） −ソフトヒープでキーが最も少ない要素を取得します
• フィボナッチヒープなどの他のヒープは、破損することなくこれらの境界のほとんどを達成しますが、重要な削除操作に一定時間の境界を提供することはできません。破損の量は、パラメーターεを選択することで制御できますが、これを低く設定すると、挿入に必要な時間が長くなります（エラー率εの場合、O（log 1 /ε））。
• より正確には、ソフトヒープによって提供される保証は次のとおりです。0〜1 / 2の固定値εの場合、任意の時点で、ヒープ内に最大ε*mの破損したキーが存在します。ここでmは挿入または破損した要素の数W。キーの一定の割合のみが現在であることを保証することはできません。 ヒープ内のキーが破損または増加しています。挿入と削除の不要なシーケンスでは、ヒープ内のすべての要素のキーが破損または破損している可能性があります。同じ場合、ヒープから抽出された一連の要素で findminを使用するという保証はありません。 削除すると、一定の割合でのみキーが破損または増加します。不運なシナリオでは、破損または増加した要素のみがヒープから抽出されます。
• 制限と予測不可能な性質にもかかわらず、ソフトヒープは決定論的アルゴリズムの設計に役立ちます。これらは、最小スパニングツリーを決定するためのこれまでで最高の複雑さを得るために実装されました。また、最適な選択アルゴリズムと、挿入ソートが高速な状況である最終位置の近くにすべての要素を設定するアルゴリズムであるニアソートアルゴリズムを簡単に構築するために実装することもできます。