DAA - Pattern di unione ottimale

Unisci un insieme di file ordinati di diversa lunghezza in un unico file ordinato. Dobbiamo trovare una soluzione ottimale, in cui il file risultante verrà generato in un tempo minimo.

Se viene fornito il numero di file ordinati, esistono molti modi per unirli in un unico file ordinato. Questa unione può essere eseguita in coppia. Quindi, questo tipo di fusione è chiamato come2-way merge patterns.

Poiché accoppiamenti diversi richiedono quantità di tempo diverse, in questa strategia vogliamo determinare un modo ottimale per unire più file insieme. Ad ogni passaggio, vengono unite due sequenze più brevi.

Per unire un file p-record file e a q-record file richiede possibilmente p + q record di movimenti, la scelta più ovvia è, unire i due file più piccoli insieme ad ogni passaggio.

I modelli di unione a due vie possono essere rappresentati da alberi di unione binari. Consideriamo un insieme din file ordinati {f₁, f₂, f₃, …, f_n}. Inizialmente, ogni elemento di questo è considerato come un albero binario a nodo singolo. Per trovare questa soluzione ottimale, viene utilizzato il seguente 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);

Alla fine di questo algoritmo, il peso del nodo radice rappresenta il costo ottimale.