配列として格納されている 2 つの最大ヒープをマージするための効率的なアルゴリズムはありますか?
36352 次
3 に答える
21
ヒープの種類によって異なります。
すべてのノードに最大 2 つの子があり、葉が最大 2 つの異なる行にある標準ヒープである場合、マージのために O(n) を超えることはできません。
2 つの配列をまとめて、それらから O(n) を取る新しいヒープを作成するだけです。
マージのパフォーマンスを向上させるために、償却された O(1) でマージできるフィボナッチ ヒープのような別のヒープ バリアントを使用できます。
更新: 挿入には O(log(n)) かかるため、最初のヒープのすべての要素を 1 つずつ 2 番目のヒープに挿入したり、その逆を行ったりする方が悪いことに注意してください。あなたのコメントが述べているように、ヒープが最初にどのように最適に構築されているかを知らないようです(これも標準のバイナリヒープの場合)
- 配列を作成し、両方のヒープの要素を任意の順序で配置します
- 最低レベルから始めます。最下位レベルにはサイズ 1 の自明な最大ヒープが含まれているため、このレベルは完了です
- レベルを上げます。「サブヒープ」の 1 つのヒープ条件が違反された場合、「サブヒープ」のルートをより大きな子と交換します。その後、レベル 2 が完了します。
- レベル 3 に移動します。ヒープ条件が違反された場合は、以前と同様に処理します。それをより大きな子と交換し、すべてがレベル 3 まで一致するまで再帰的に処理します
- ...
- トップに到達すると、O(n) に新しいヒープが作成されます。
ここでは証明を省略しますが、ヒープ状態を再確立するために多くのコンテンツを交換する必要のない最下位レベルでほとんどのヒープを実行したため、これを説明できます。はるかに小さい「サブヒープ」で操作しました。これは、すべての要素をヒープの1つに挿入する場合よりもはるかに優れています=>その後、毎回O(n)かかるヒープ全体で毎回操作します.
更新 2:二項ヒープは O(log(n)) でのマージを許可し、O(log(n)^2) 要件に準拠します。
于 2009-10-20T16:02:19.330 に答える
9
サイズが n と k の 2 つのバイナリ ヒープは、O(log n * log k) 回の比較でマージできます。見る
于 2009-11-02T02:43:22.333 に答える
1
この場合、あなたが探しているのは二項ヒープだと思います。
二項ヒープは、マージ可能なヒープ ファミリーのメンバーである二項ツリーのコレクションです。ヒープ内に合計 n 個のアイテムがある 2 つ以上の二項ヒープでの和集合 (マージ) の最悪の場合の実行時間は O(lg n) です。
詳細については、 http://en.wikipedia.org/wiki/Binomial_heap を参照してください。
于 2014-03-31T19:23:15.817 に答える