DAA - Padrão de fusão ideal

Mescle um conjunto de arquivos classificados de comprimentos diferentes em um único arquivo classificado. Precisamos encontrar uma solução ótima, onde o arquivo resultante será gerado em tempo mínimo.

Se o número de arquivos classificados for fornecido, há muitas maneiras de mesclá-los em um único arquivo classificado. Esta fusão pode ser realizada em pares. Portanto, este tipo de fusão é chamado de2-way merge patterns.

Como diferentes emparelhamentos requerem diferentes períodos de tempo, nesta estratégia queremos determinar uma maneira ideal de mesclar muitos arquivos. Em cada etapa, duas sequências mais curtas são mescladas.

Para fundir um p-record file e um q-record file requer possivelmente p + q gravar movimentos, sendo a escolha óbvia, mesclar os dois arquivos menores em cada etapa.

Os padrões de mesclagem bidirecional podem ser representados por árvores de mesclagem binárias. Vamos considerar um conjunto den arquivos classificados {f₁, f₂, f₃, …, f_n}. Inicialmente, cada elemento disso é considerado uma árvore binária de nó único. Para encontrar essa solução ideal, o seguinte algoritmo é usado.

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

No final deste algoritmo, o peso do nó raiz representa o custo ótimo.