私が知っているように、2 つのヒープをマージするために使用される二項ヒープまたはいわゆるマージ可能なヒープが存在します。私の質問は、これらのヒープを 1 つのヒープに動的にマージする代わりに、これら 2 つのヒープを 1 つの大きな配列にコピーしてからヒープ構築手順を実行すると、それは良いアプローチでしょうか?
ヒープ操作だけで2つのヒープを使用して1つのヒープを作成する方法がわからないためです。それが良い方法でないかどうか教えてください。または、可能であれば、マージ操作を伴う二項ヒープが実装されているリンクを教えてください。
考えてみれば、他のヒープの順序付けに埋め込まれたすべての情報を捨てて 1 つのヒープを作成することは、おそらく最適ではありません。最悪の場合、ヒープ 2 のすべてのアイテムをヒープ 1 に追加する必要があります。これは、まったく新しいヒープを最初から作成する作業の半分にすぎません。
しかし、実際には、それよりもはるかに優れた方法を実行できます。整形式の 2 つのヒープをマージするには、他のヒープのツリーでルートの 1 つの挿入ポイントを見つけて、そのポイントに挿入するだけです。これ以上の作業は必要ありません。これで作業は完了ln Nです。詳細なアルゴリズムについては、こちらを参照してください。
これで問題が解決し、正しいヒープが得られますが、効率的ではありません。
nゼロから要素の [binary] ヒープを作成するのは ですがO(n)、2 つの既存の 2 項ヒープをマージO(logn)するのはです。
Brodal キューと Brodal-Okasaki キュー (ブートストラップされたスキュー二項ヒープ) は、O(1) の挿入、マージ、findMin、および O(log n) の deleteMin をサポートし、マージ可能なヒープに最適な最悪の場合の漸近境界を提供します。Brodal キューは一時的なものであり、効率的な削除と減少キーをサポートします。Brodal-Okasaki キューはコンフルエントに永続的です (実際には純粋に機能的です) が、delete または reduceKey をサポートしていません。残念なことに、Brodal と Okasaki は、これらの実装はどちらも実際には非効率的であると述べており、Brodal は彼のキューが複雑すぎていずれにしても実用的ではないと考えています。
フィボナッチ ヒープは、同様の償却された (ただし、最悪の場合ではない) 境界を示し、償却されたコンテキストではより効率的で実用的である可能性があります。ペアリング ヒープも良い選択肢です。ウィキペディアによると、それらの正確な境界は不明ですが、実際には非常にうまく機能します。