「アルゴリズムの紹介」から f-heap を学んでいますが、「キーの減少」操作は本当に混乱します。なぜこれに「カスケードカット」が必要なのですか?
この操作が削除された場合:
- make-heap()、insert()、minimum()、および union() のコストは明らかに変更されていません
- O(n(H)) 'consolidate' 操作では、ほとんどのルート ツリーのコストは、ルート リストに追加されたときに支払うことができるため、extract-min() は引き続き O(D(n)) です。残りの費用 O(D(n))
- 減少キー (): 明らかに O(1)
D(n) については、正確に説明することはできませんが、まだ O(lgn) であると思います。「cascading-cut」がないため、ノードは少し後でルート リストに移動される可能性があります。父親の下に隠れても効率には影響しません。少なくとも、これで状況が悪化することはありません。
私の下手な英語で申し訳ありません:(
誰でも助けることができますか？ありがとう