algorithm - フィボナッチ ヒープのキーを減らす方法を理解するのに助けが必要

Question

フィボナッチ ヒープ操作を実装する方法を理解しようとしています。次のヒープがあるとします。

たとえば、35 を 27 に減らすにはどうすればよいでしょうか。27 は 30 以下であるため、順序は保持されないため、ヒープを再構築する必要があります。では、27 はどこに行くのでしょうか。5歳未満？

Answer 1

フィボナッチ ヒープでは、recrease-key は、キーが親のキーより下に減少するツリーからノードを実際に切り取ります。あなたの場合、ノードはルートリストにシングルトンノードとして配置されます。

より一般的には、キーの減少は次のように機能します。

1. キーを減らします。
2. ノードの新しいキーがそ​​の親のキーよりも大きい場合は、停止します。
3. ノードがルートの場合は停止します。
4. ノードのマークを外し、親から切り取ります。
5. 親がマークされていない場合は、マークします。
6. 親がマークされている場合は、(3) に進みます。

お役に立てれば！