ソフトヒープとは？償却定数時間を実現するヒープ構造の仕組みと応用

ソフトヒープ（soft heap）は、一般的なヒープデータ構造の変種であり、5種類の操作を償却定数時間で実行できることを特徴とします。この高い処理速度は、ヒープ内の一定数までのキーを意図的に「破壊」、すなわち値を増加させるという巧妙なトレードオフによって実現されています。

定数時間で実行できる操作

• create(s) − 新しいソフトヒープ s を作成する
• insert(s, y) − ソフトヒープ s に要素 y を挿入する
• meld(s, s′) − 2つのソフトヒープ s と s′ を1つに統合し、元の2つを破棄する
• delete(s, y) − ソフトヒープ s から要素 y を削除する
• findmin(s) − ソフトヒープ s 内で最小のキーを持つ要素を取得する

他のヒープ構造との比較

フィボナッチヒープなどの他のヒープ構造も、キーを破壊することなく上記の計算量の多くを実現できます。しかし、クリティカルな delete 操作については定数時間の保証を提供できません。ここがソフトヒープの大きな優位点です。

破壊率の制御とコスト

キーが破壊される量は、パラメータ ε（イプシロン）の選択によって制御できます。ただし、ε を小さく設定するほど挿入に必要な時間が増大し、誤り率 ε に対して O(log 1/ε) の時間がかかります。

ソフトヒープが提供する保証

より正確には、ソフトヒープの保証は次のように述べられます。0 から 1/2 の間の固定値 ε に対して、任意の時点における破壊されたキーの数は最大 ε・m 個です。ここで m は、挿入または破壊された要素の総数を表します。

ただし、以下の2点に注意が必要です。

• 現在ヒープに存在するキーのうち固定割合のみが破壊されているとは保証されません。挿入と削除が不運な順序で行われた場合、ヒープ内のすべての要素のキーが増加（破壊）している可能性があります。
• findmin と delete を用いてヒープから抽出される一連の要素についても、破壊されたキーを持つ要素の割合が固定であるとは保証されません。最悪の場合、破壊された要素だけがヒープから取り出されることもあり得ます。

ソフトヒープの応用

こうした限界や予測不可能性があるにもかかわらず、ソフトヒープは決定的アルゴリズムの設計において非常に有用です。具体的には、以下のような応用例があります。

• 最小全域木（MST）：ソフトヒープを用いることで、現時点で最良の計算量を持つ最小全域木判定アルゴリズムが実現されています。
• 選択アルゴリズム：最適な選択（k番目の要素の抽出）アルゴリズムを簡潔に構築できます。
• ニアソート（near-sorting）アルゴリズム：各要素を最終的な位置のごく近くまで整列させるアルゴリズムです。この状態では挿入ソートが高速に動作するため、実用的な後段処理と組み合わせられます。