2 つのヒープ配列を 1 つのバランスの取れたヒープ配列にマージし、線形の複雑さを維持するにはどうすればよいですか? ヒープのマージについて読んだ資料の多くは、O(nlogn) を使用します。
1613 次
2 に答える
0
それぞれサイズ N の 2 つのヒープが与えられます。各ヒープは配列として表すことができます親と子の関係 を参照してください。したがって、ヒープ順の 2 つの配列があります。1 つの配列のすべての要素をもう 1 つの配列の末尾に追加して、これら 2 つの配列を 1 つに連結する必要があります。
これで、サイズが 2N の配列が 1 つになりましたが、ヒープ順ではありません。配列ヒープを順序付けするには、線形数の比較が必要なため、線形時間がかかります。(ボトムアップのヒープ構築 - O(n) でヒープを構築する順序を参照)
于 2014-07-23T20:39:50.350 に答える