バイナリ ヒープは 2 つの子 (ツリー表現) しか持つことができず、二項ヒープは任意の数の子を持つことができるという構造の違いに関係なく、バイナリ ヒープと二項ヒープの主な違いを知る必要があります。
実際、最初の子が 1 つのノードに 2 番目に 2 番目に 2 番目に 4 番目にあるというように二項ツリー構造を編成する際に何が特別なのか疑問に思っています。
2 つの子を制限せずにヒープに通常のツリーを使用し、結合手順を適用して、1 つのヒープを他のヒープの左側の子にする場合はどうなるでしょうか。
二項ヒープと二項ヒープの主な違いは、ヒープの構造です。バイナリヒープでは、ヒープは単一のツリーであり、完全なバイナリツリーです。二項ヒープでは、ヒープは小さなツリー（つまり、木の森）のコレクションであり、それぞれが二項ツリーです。完全な二分木は任意の数の要素を保持するように構築できますが、ある次数nの二項ツリーの要素の数は常に2nです。。したがって、バイナリヒープをバックアップするために必要な完全なバイナリツリーは1つだけですが、二項ヒープをバックアップするために複数の二項ツリーが必要になる場合があります。興味深いことに、二項ヒープで使用される二項ツリーの順序は、フォレスト内の要素数のバイナリ表現で設定された1ビットに対応します。
二項ヒープをそのまま編成する理由は、次数nの二項ツリーには常に正確に2n個のノードがあるためです。これにより、二項ツリーの構造を実際に検査しなくても、二項ツリーの要素数を推測できます。一方、高さhの完全な二分木には、最後の行の入力方法に応じて、ノードの数が可変になる場合があります。各子が非常に正確に定義された構造を持っている必要があるという事実は、子の数が最大でO（log n）であることを証明するためにも使用できます。ここで、nはヒープ内のノードの総数です。 delete-minのコストはそれほど大きくありません。
この背後にある重要な詳細は、二項ヒープはk個の子を持つツリーではないということです。それは厳密に次のように定義されている木です
（技術的には、注文0の特別な場合はここでは必要ありません）。あなたはここでこれを見ることができます：
各順序のツリーは1つだけであり、ノードの数や位置に柔軟性がまったくないことに注意してください。
ただし、重要な代替定義は次のとおりです。
（これらが同等である理由を確認するために少し時間を取ってください）。この2番目の定義を使用すると、ツリー内のノードの数が2nであることを示す簡単な帰納法の証明になります。基本ケースとして、次数0のツリーには、必要に応じて2 0 =1ノードがあります。帰納的ステップの場合、次数n -1のツリーが2つある場合、必要に応じて、それらは集合的に2 n-1 + 2 n-1 = 2nノードになります。したがって、次数nの二項ツリー内のノードの総数は正確に2nです。
最後の段落で説明しているヒープのアイデアは、必ずしも効率的なランタイムにつながるとは限りません。特に、分岐係数が大きく、他の構造上の制約がないツリーがある場合、理論的には、（n-1）個の子を持つ単一ノードで構成されるnノードのヒープを構築できます。その場合、ヒープから最小要素を削除した後、すべてのn-1の子を調べて、どれが新しい最小であるかを判別し、O（n）の実行時間を与える必要があります。完全な二分木、二項木などのツリーに対する他の構造上の制約は、この最悪のケースが発生しないことを保証します。
お役に立てれば！
バイナリ ヒープは、同じランクの任意の 2 つの子フル バイナリ ツリーをルート ノードに結合することによって作成できます。少し自由なスタイルの木です - 一部の葉は右から切り取ることができます
ランク N の二項ツリーは、木の森ではありません。これは、ランク N-1、N-2、...、1、0 の二項ツリーに接続されたルート ノードです。二項ヒープは、構造が完全に固定されたツリーです。
(申し訳ありませんが、誰かが Wiki を間違った方法で読んでいたのです。) 次数 k の二項ツリーにはルート ノードがあり、その子ノードは次数 k−1、k−2、...、2、1、の二項ツリーのルートです。 0 (この順序で)。