私は 'introduction to algorithms'からf-heapを学んでいますが、 'reduce-key'操作は本当に私を混乱させます - なぜこれにはカスケードカットが必要ですか？フィボナッチヒープにカスケードカットが必要なのはなぜですか？
この操作が削除された場合：
D（n）は正確には説明できませんが、まだカスケードカットされていないO（lgn）、cuzだと思います。ノードはちょっと後でルートリストに移動します任意のノードはその父親の下に隠れるは効率に影響しません。少なくとも、これは状況を悪化させません。
することは、私の下手な英語をお詫び:(
誰でも助けることができる？カスケードカット用 感謝
理由が低い（n）はDを維持することです。それはあなたが任意の数のを許可した場合ことが判明しますノードがツリーから切り取られる場合、D（n）は線形になり、削除と削除minが線形時間をとることができます。
直感的に、順序kのツリー内のノードの数をこのようにして、統合されたヒープ内に対数的に多くのツリーしか持たせることはできません。木から、あなたはこの保証を失います。具体的には、注文kの木を取ってから、すべての孫を切り取ることができます。これはk個の子供を持つ木を残します。それぞれの子は葉です。その結果、k + 1個のノードを持つ順序kの木を作成することができます。これは、最悪の場合、D（n）がO（log n）ではなくn-1になるように、すべてのノードを保持するためにn-1次の木が必要であることを意味します。
希望すると便利です。
ええ、そうです。この誤解を招くD（n）は問題を引き起こしますが、D（n）の子供の親が抽出されたときには表示されません（私が書いた理由は上記です）。親が**統合中に親を選択しているときに**表示されます - 間違ったD（）はアンバランスを引き起こします。今度は、カスカットしたキーを減らした後、私がカスカットしたのと同じように、D（n）をすべて維持することができれば、D（）は子供の量よりも小さくなる可能性がある抽出分の値は依然としてO（lgn）である。同じD（）を正確に維持するのは難しいですが、バランスを維持する別の方法があると思います。 – exprosic
すべてのノードにはSがあります。最初はノードのサイズです。明らかに、それは2のべき乗 - 2進表記で10 - 000です。その子が削除され、**ビット数**（[log2（S）]）が減少すると（1000-> 111,1011-> 101など）、その差は親に報告されます。差異が親の[log2（s）]を減少させるのに十分大きい場合、その差は祖父母に報告されます。 – exprosic
同じことは、ノードの親ノードへの減少を隠すことですが、O（1）時間にはS（またはD）と実際のノード数（Sは少なくともS/2ノードを持ちます） S/Dを使用してバランスを保つ（同じD、または同じ[log2（S）]ノードを結合する）。そうですか？ – exprosic
大きな質問です。親の位置にあるすべての情報を放棄するのは非常に直感的ではないようです。 –