これをよく知っている人は、実際の質問について以下の太字のテキストを読んでください.
補助機能の序文:
同じランクの 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) ではないでしょうか?
おそらく、ここでいくつかの重要な理解が欠けています。どんな助けでも大歓迎です！私の理解のどこが間違っていたのか教えていただければ、さらに感謝します:)