DAA-最適なマージパターン

異なる長さのソートされたファイルのセットを単一のソートされたファイルにマージします。結果のファイルが最小時間で生成される最適なソリューションを見つける必要があります。

ソートされたファイルの数が指定されている場合、それらを1つのソートされたファイルにマージする方法はたくさんあります。このマージはペアごとに実行できます。したがって、このタイプのマージは次のように呼ばれます。2-way merge patterns。

ペアリングが異なれば必要な時間も異なるため、この戦略では、多くのファイルをマージする最適な方法を決定する必要があります。各ステップで、2つの最短シーケンスがマージされます。

マージするには p-record file と q-record file おそらく必要です p + q レコードの移動は、当然の選択ですが、各ステップで2つの最小のファイルをマージします。

双方向のマージパターンは、バイナリマージツリーで表すことができます。のセットを考えてみましょうn ソートされたファイル {f₁, f₂, f₃, …, f_n}。最初は、この各要素は単一ノードの二分木と見なされます。この最適解を見つけるために、次のアルゴリズムが使用されます。

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

このアルゴリズムの最後では、ルートノードの重みが最適なコストを表します。