問題タブ [binomial-heap]

Binomial Heap の Python 実装を探していますが、コードに reduceKey が実装されていないことに気付きました。二項ヒープでは、誰もreduceKeyを実装していないのはなぜですか?

これをよく知っている人は、実際の質問について以下の太字のテキストを読んでください.

補助機能の序文:

同じランクの 2 つの二項ツリーをマージすることは O(1) であることを知っています。必要なのは、T1 のヘッドをもう一方の子として追加することだけだからです。また、マージの「キャリーオーバー」効果が適用されるため、二項ヒープ内の最小次数ツリー以下の次数のツリーを挿入することは O(logN) であることも知っています。T_0、T_1、T_2、...、T_n (添え字は次数) の二項ヒープを想像してください。次数 0 の新しい T' を追加します。同じ順序。n = log(N) を知っています。

マージ機能自体:

マージ関数では、マージソートのような方法で、2 つのヒープがツリーごとに新しいヒープ ツリーに追加されます。いずれかのヒープの最下位ツリーを新しいヒープに追加し、両方の順序が同じ場合は、それをマージ (O(1)) し、構築後に結果のツリーに挿入 (O(logN)) します。再帰的に。最下位のツリーを最初に挿入するため、マージでは常に、新しいヒープの最初のツリーと同じかそれ以下のツリーが挿入されます。

混乱が起こる場所：

マージ関数が O(logN*logN) ではなく O(logN) である理由がわかりません。各挿入は O(logN) であることがわかっており、logN ツリーがあります。ここで、N = N1+N2 で、N1 と N2 は各開始ヒープ内の要素の数です。構造に 2 つのヒープがあり、新しいヒープに挿入するたびに挿入のキャリーオーバー効果が発生する状況につながる場合、O(logN * logN) ではないでしょうか?

おそらく、ここでいくつかの重要な理解が欠けています。どんな助けでも大歓迎です！私の理解のどこが間違っていたのか教えていただければ、さらに感謝します:)

ウィキペディアによると、二項ヒープでの挿入操作の償却時間は O(1) です。単一の挿入操作の場合、時間の複雑さは O(log n) です。しかし、その償却時間はどのようにして O(1) になるのでしょうか?