DAA - Optimal Birleştirme Modeli

Farklı uzunluktaki bir dizi sıralı dosyayı tek bir sıralı dosyada birleştirin. Ortaya çıkan dosyanın minimum sürede oluşturulacağı optimum bir çözüm bulmamız gerekiyor.

Sıralanan dosyaların sayısı belirtilmişse, bunları tek bir sıralı dosyada birleştirmenin birçok yolu vardır. Bu birleştirme çiftler halinde yapılabilir. Bu nedenle, bu tür bir birleştirme,2-way merge patterns.

Farklı eşlemeler farklı miktarlarda zaman gerektirdiğinden, bu stratejide birçok dosyayı bir araya getirmenin en uygun yolunu belirlemek istiyoruz. Her adımda, en kısa iki dizi birleştirilir.

Birleştirmek için p-record file ve bir q-record file muhtemelen gerektirir p + q kayıt hareketleri, bariz seçim, her adımda en küçük iki dosyayı birleştirmektir.

İki yönlü birleştirme desenleri, ikili birleştirme ağaçları ile temsil edilebilir. Bir dizi düşünelimn sıralı dosyalar {f₁, f₂, f₃, …, f_n}. Başlangıçta, bunun her bir öğesi tek düğümlü ikili ağaç olarak kabul edilir. Bu en uygun çözümü bulmak için aşağıdaki algoritma kullanılır.

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

Bu algoritmanın sonunda, kök düğümün ağırlığı optimum maliyeti temsil eder.