Quake Heaps

日曜日と今日、やや大きな地震が関東近郊でありました。今日の地震は、quake heap を読んでいる最中だったので、驚きました。以下では、不謹慎な記事を含んでいるかもしれません。アルゴリズムの動作の比喩なので、ご容赦ください。

Queak heap は、wikipedia:en:Timothy M. Chan が最近報告したデータ構造です。次の操作を備えています。wikipedia:en:Fibonacci heap と同程度の計算コストになっています。

• insert(k, x): キーkを持つ要素xを追加する; O(1) 時間
• decrease_key(k', x): 要素xのキーをk'に減らす; O(1) 償却時間
• delete_min(): 最小のキーを持つ要素を削除する; O(log n) 償却時間

「Quake」を冠する理由は、ある条件が揃うと「seismic event」が発生するからです。Quake heap は、いくつかの tournament tree の集まりです。decrease_key を繰り返すと出次数１のノードがいっぱい増えます。増えすぎたら、葉っぱから「ある段数より上のノード」は全部びゃーっと削除してしまいます。こうすると、低い高さの木がいっぱいできてしまいますが、これで良いのです。面白いですね。

このレポートを読むと、最近のヒープの簡単な動向がうかがえます。それから、amortized analysis の簡単な復習ができました。ポテンシャル関数をどのように設定するかが大切なんですね。