optimal merge patterns

) انماط الدمج الامثل (Optimal Merge Pattern)

المسألة هي دمج n من الملفات المرتبة على شكل ازواج وتوليد ملف واحد مرتب بأقل عدد ممكن من تحريكات السجلات. لأن هذه المسألة تستدعي الترتيب مابين أزواج الملفات المراد دمجها لذلك فهي تطابق نموذج الترتيب.
قاعدة الطماع:- لتقليص حركة السجلات، ادمج الملفين الاقل حجما عند كل خطوة أولا.

مثال/ [F1..F5]=(20, 30, 10, 5, 30)


اذا كانت di ? بعد العقدة الخارجية للملف Fi.
qi ? طول الملف Fi.
فأن العدد الكلي لتحريكات السجلات لشجرة الدمج الثنائية هذه تكون

وفيما يلي خوارزمية توليد شجرة الدمج الثنائية:-
Algorithm Optimal_Merge ( list, n):
Input: An array list of n single node binary tree – each
represents a file – sorted in nondecreasing order
according to their lengths.
Output: A binary merge tree T.
1. for i 1 to n-1
2. create a new node v
3. c least(list)
4. c` least(list)
5. length(v) length(c)+length(c`)
6. lchild(v) c
7. rchild(v) c`
8. insert(list, v)
9. end for
10. T least(list)
11. return T
في البداية كل شجرة في القائمة list تمتلك بالضبط عقدة واحدة. هذه العقدة هي عقدة خارجية حيث يحتوي فيها حقلي lchild و rchild قيما صفرية اما الحقل length فيحتوي على طول احد الملفات المراد دمجها. هذه الخوارزمية تستخدم دالتين هما least و insert. الدالة least تقوم بايجاد شجرة في القائمة جذرها يمتلك الطول الاقل وتعيد هذه الدالة مؤشر الى هذه الشجرة التي يتم حذفها بعد ذلك من القائمة. الدالة insert تقوم بحشر الشجرة التي جذرها v الى القائمة list. تستخدم شجرة الدمج الثنائية الناتجة في نهاية الخوارزمية لتحديد اي الملفات يتم دمجها اولا حيث يتم الدمج على تلك الملفات التي تمتلك العمق الاكبر في الشجرة.

تعقيدات الوقت للخوارزمية
تتكرر حلقة for الرئيسية في الخوارزمية السابقة n-1 من المرات، وفي حال الاحتفاظ بالقائمة list مرتبة تصاعديا نسبة الى قيم الاطوال في الجذور فان الدالة least تتطلب فقط ?(1) من الوقت والدالة insert يمكن انجازها في وقت هو ?(n). اذن الوقت الكلي المستغرق هو ?(n2).