max-heap - 2 つの最大ヒープをマージする

Question

2 つの最大ヒープをマージする最も効率的なアルゴリズムを見つける必要があります。

いくつかの重要な事実: ヒープはバイナリ ツリーとして表されます。つまり、各ノードには 3 つのフィールド (値 (キー)、右の子へのポインター、左の子へのポインター) があります。

私の考え: 2 番目のヒープの最後の葉を取り、それを新しいヒープのルートとして配置します。したがって、左側の子が正当な最大ヒープであり、右側の子が正当な最大ヒープである場合、新しいヒープを取得します。(私の意見では) 問題は、ルートが最大要素ではないという事実だけです。そのため、ルートから関数Max-Heapifyを実行でき、問題を解決できると思います。

最悪の場合の総実行時間 - O(logn) - リーフをルートとして作成するのはO(1)であり、Max-HeapifyはO(logn)であるためです。

あなたはそれについてどう思いますか？私は正しいですか？2つの最大ヒープをマージするためのより効率的なアルゴリズムはありますか? (表現が二分木であることを考慮してください)

Answer 1

提案されたアプローチには2つの問題があります。1 つ目は表現です。通常、ヒープは、O(n)インターリーブ操作が必要なポインターを持つ個々のノードとしてではなく、配列として表現されます。

ただし、配列ストレージの前に問題がなくても、考慮すべき shape プロパティがあります。運がよければ、左と右のヒープは、結果が有効なヒープ (つまり、葉の深さが最大で 1 異なり、より深いすべての葉が存在する場所) になるのに適切なサイズにはなりません。左）。

バイナリ ヒープのマージの詳細については、2 つの最大ヒープをマージするアルゴリズムを参照してください。. ただし、配列表現を使用していない場合は、そこに記載されているすべてが必ずしも適用されるわけではありません。