DAA - Patrón de fusión óptimo

Combine un conjunto de archivos ordenados de diferente longitud en un solo archivo ordenado. Necesitamos encontrar una solución óptima, donde el archivo resultante se generará en un tiempo mínimo.

Si se proporciona el número de archivos ordenados, hay muchas formas de combinarlos en un solo archivo ordenado. Esta combinación se puede realizar por parejas. Por lo tanto, este tipo de fusión se denomina2-way merge patterns.

Dado que los diferentes emparejamientos requieren diferentes cantidades de tiempo, en esta estrategia queremos determinar una forma óptima de fusionar muchos archivos. En cada paso, se fusionan dos secuencias más cortas.

Para fusionar un p-record file y un q-record file requiere posiblemente p + q movimientos de registro, siendo la elección obvia fusionar los dos archivos más pequeños en cada paso.

Los patrones de fusión bidireccionales se pueden representar mediante árboles de fusión binarios. Consideremos un conjunto den archivos ordenados {f₁, f₂, f₃, …, f_n}. Inicialmente, cada elemento de esto se considera como un árbol binario de un solo nodo. Para encontrar esta solución óptima, se utiliza el siguiente algoritmo.

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);

Al final de este algoritmo, el peso del nodo raíz representa el costo óptimo.