ヒープをマージするための次のアルゴリズムが正しくない理由を誰かが説明できますか?
2 つの (最大) ヒープ H1 と H2 があるとします。
それらをマージするには:
キー値が負の無限大である人工ダミー ノードを作成し、H1 と H2 を子としてアタッチしてルートに配置します。次に、最終的にルートをリーフ位置にスワップする O(log n) バブル ダウン ステップを実行し、そこで最終的に削除されます。結果の構造はマージされたヒープです。
ウィキペディアと他の場所の両方で、2 つの同じサイズのヒープをマージすることは Theta(n) 操作であるという主張を見てきましたが、これは私が上に書いたことと矛盾しています。
少なくともヒープが通常実装されているため (ノードの配置にリンクが暗黙的に含まれている)、ほとんど無視しているように見える部分 (「H1 と H2 が子としてアタッチされている」) は、それ自体で線形の複雑さを持っています。
ヒープは通常実装されるため、各要素 N がその子として要素 2N および 2N+1 を持つ線形コレクション (たとえば、配列) があります (たとえば、1 ベースの配列では、要素 1 の子は要素 2 です)。および 3 であり、要素 2 の子は 4 および 5 です)。したがって、マージ操作の開始点に到達する前に、2 つのヒープの要素をインターリーブする必要があります。
明示的にリンクされたバイナリ ツリーから始めた場合 (たとえば、バイナリ サーチ ツリーの順序付けではなく、ヒープ スタイルの規則に従っているだけ) は正しいでしょう。マージは対数の複雑さで実行できますが、元の記事は疑わしいものです。そのような構造を指すことを意図しています。
ツリーとして実装している場合、ソリューションは正しいです。しかし、Jerry が述べたように、配列ベースのヒープのマージはサブリニア時間では実行できません。
マージの頻度とサイズによっては、仮想ヒープを使用することをお勧めします。ヒープのヒープとして実装できます（配列を使用）。数回のマージの後、複数の内部ヒープを 1 つの大きなヒープに遅延マージできます。