DAA - Mẫu hợp nhất tối ưu

Hợp nhất một tập hợp các tệp được sắp xếp có độ dài khác nhau thành một tệp được sắp xếp. Chúng tôi cần tìm một giải pháp tối ưu, nơi tệp kết quả sẽ được tạo trong thời gian tối thiểu.

Nếu số lượng tệp được sắp xếp được cung cấp, có nhiều cách để hợp nhất chúng thành một tệp được sắp xếp duy nhất. Sự hợp nhất này có thể được thực hiện theo cặp khôn ngoan. Do đó, kiểu hợp nhất này được gọi là2-way merge patterns.

Vì, các quá trình ghép nối khác nhau yêu cầu lượng thời gian khác nhau, trong chiến lược này, chúng tôi muốn xác định một cách tối ưu để hợp nhất nhiều tệp với nhau. Ở mỗi bước, hai chuỗi ngắn nhất được hợp nhất.

Để hợp nhất một p-record file và một q-record file yêu cầu có thể p + q kỷ lục di chuyển, lựa chọn hiển nhiên là hợp nhất hai tệp nhỏ nhất với nhau ở mỗi bước.

Các mẫu hợp nhất hai chiều có thể được biểu diễn bằng cây hợp nhất nhị phân. Hãy để chúng tôi xem xét một tập hợpn các tệp được sắp xếp {f₁, f₂, f₃, …, f_n}. Ban đầu, mỗi phần tử này được coi là một cây nhị phân nút đơn. Để tìm giải pháp tối ưu này, thuật toán sau được sử dụng.

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

Khi kết thúc thuật toán này, trọng số của nút gốc đại diện cho chi phí tối ưu.