Data Structures Algorithms 简明教程
Optimal Merge Pattern Algorithm
将一组不同长度的已排序文件合并为一个已排序文件。我们需找到一个最优解决方案，以便在最短时间内生成结果文件。
如果给出了已排序文件的数量，则有许多方法可以将它们合并为一个已排序文件。此合并可以逐对进行。因此，这种类型的合并称为 2-way merge patterns 。
由于不同的配对需要不同的时间，在此策略中，我们要确定一种将许多文件合并在一起的最优方法。在每一步中，都会合并两个最短序列。
合并一个 p-record file 和一个 q-record file 可能需要 p + q 条记录移动，显而易见的做法是，在每一步将两个最小的文件合并在一起。
双向合并模式可以用二进制合并树表示。我们来考虑一组 n 个已排序文件 {f1, f2, f3, …, fn} 。最初，此组的每个元素都被视为一颗单节点二叉树。要找到此最优解决方案，请使用以下算法。
Pseudocode
以下是最优合并模式算法的伪代码 -
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);在此算法结束时，根节点的权重表示最优成本。
Examples
我们来考虑给定的文件 f1、f2、f3、f4 和 f5，它们各自有 20、30、10、5 和 30 个元素。
如果合并操作按照提供的序列执行，则
M1 = merge f1 and f2 ⇒ 20 + 30 = 50
M2 = merge M1 and f3 ⇒ 50 + 10 = 60
M3 = merge M2 and f4 ⇒ 60 + 5 = 65
M4 = merge M3 and f5 ⇒ 65 + 30 = 95
因此，操作总数为
50 + 60 + 65 + 95 = 270
现在，问题来了，有没有更好的解决方案？
按升序对数字进行排序，我们可以得到以下序列 −
f4, f3, f1, f2, f5
因此，可以对这个序列进行合并操作
M1 = merge f4 and f3 ⇒ 5 + 10 = 15
M2 = merge M1 and f1 ⇒ 15 + 20 = 35
M3 = merge M2 and f2 ⇒ 35 + 30 = 65
M4 = merge M3 and f5 ⇒ 65 + 30 = 95
因此，操作总数为
15 + 35 + 65 + 95 = 210
显然，这比前一个更好。
在此背景下，我们现在将使用此算法来解决问题。
