10. الأكوام
يناقش هذا الفصل تنفيذين لبنية بيانات طابور الأولوية (priority Queue) المفيدة إلى حدٍّ بعيد. وكلتا البنيتين هما نوعٌ خاص من الشجرة الثنائية (binary tree) يسمّى الكومة (heap)، أي «كومة غير منظَّمة». ويقابل ذلك أشجار البحث الثنائية (binary search trees) التي يمكن تصوّرها كومةً منظَّمة إلى حدٍّ كبير. أمّا التنفيذ الأول للكومة فيستعمل مصفوفة (array) لمحاكاة شجرة ثنائية كاملة. وهذا التنفيذ شديد السرعة يشكّل أساس أحد أسرع خوارزميات الفرز (sorting) المعروفة، وهي الفرز بالكومة (heapsort) (انظر القسم 11.1.3). أمّا التنفيذ الثاني فيقوم على أشجار ثنائية أكثر مرونة. وهو يدعم عملية التي تتيح لطابور الأولوية أن يمتصّ عناصر طابور أولوية ثانٍ .
الأقسام الفرعية
10.1 BinaryHeap: شجرة ثنائية ضمنية
الأقسام الفرعية
10.1 BinaryHeap: شجرة ثنائية ضمنية
يقوم تنفيذنا الأول لطابور (أولوية) على تقنيةٍ عمرها أكثر من أربعمئة عام. تتيح لنا طريقة Eytzinger تمثيل شجرة ثنائية كاملة بوصفها مصفوفة، بترتيب عقد الشجرة في تسلسلٍ بالعرض (breadth-first order) (انظر القسم 6.1.2). وبهذه الطريقة، يُخزَّن الجذر عند الموضع 0، وتُخزَّن الابنة اليسرى للجذر عند الموضع 1، وتُخزَّن الابنة اليمنى للجذر عند الموضع 2، وتُخزَّن ابنة الابنة اليسرى للجذر عند الموضع 3، وهكذا. انظر الشكل 10.1.
وإذا طبّقنا طريقة Eytzinger على شجرةٍ كبيرة بما يكفي، تظهر بعض الأنماط. فالابنة اليسرى للعقدة ذات الفهرس تقع عند الفهرس ، والابنة اليمنى للعقدة ذات الفهرس تقع عند الفهرس . أمّا الأمّ (parent) للعقدة ذات الفهرس فتقع عند الفهرس .
int left(int i) {
return 2*i + 1;
}
int right(int i) {
return 2*i + 2;
}
int parent(int i) {
return (i-1)/2;
}
يستخدم BinaryHeap هذه التقنيةَ لتمثيل شجرة ثنائية كاملة ضمنيًّا، تكون فيها العناصر مرتّبة ترتيب كومة (heap-ordered): فالقيمة المخزَّنة عند أي فهرس ليست أصغر من القيمة المخزَّنة عند الفهرس ، باستثناء قيمة الجذر، . ويترتّب على ذلك أنّ أصغر قيمة في طابور الأولوية تُخزَّن عند الموضع 0 (الجذر). أمّا في BinaryHeap، فتُخزَّن العناصر الـ في مصفوفة :
T[] a;
int n;
وتنفيذ العملية مباشرٌ إلى حدٍّ كبير. فكما في جميع البنى المعتمدة على المصفوفات، نتحقّق أولًا مما إذا كانت ممتلئة (بالتحقّق مما إذا كان )، وإذا كانت كذلك فإنّنا نُكبِّر . ثمّ نضع عند الموضع ونزيد . وفي هذه المرحلة، لم يبقَ سوى ضمان الحفاظ على خاصية الكومة. ونفعل ذلك بتبديل مع أمّه تكرارًا حتى تصير ليست أصغر من أمّها. انظر الشكل 10.2.
boolean add(T x) {
if (n + 1 > a.length) resize();
a[n++] = x;
bubbleUp(n-1);
return true;
}
void bubbleUp(int i) {
int p = parent(i);
while (i > 0 && compare(a[i], a[p]) < 0) {
swap(i,p);
i = p;
p = parent(i);
}
}
أمّا تنفيذ العملية ، التي تزيل أصغر قيمة من الكومة، فهو أعقد قليلًا. فنحن نعرف أين تقع أصغر قيمة (عند الجذر)، لكنّنا بحاجة إلى استبدالها بعد إزالتها والحرص على الحفاظ على خاصية الكومة. وأيسر طريقة للقيام بذلك هي استبدال الجذر بالقيمة ، ثمّ حذف تلك القيمة، وإنقاص . للأسف، فإنّ عنصر الجذر الجديد على الأرجح ليس أصغر عنصر، لذا يلزم نقله إلى الأسفل. ونفعل ذلك بمقارنة هذا العنصر بابنتيه تكرارًا. فإن كان أصغر الثلاثة فقد انتهينا. وإلّا فبدّلنا هذا العنصر مع أصغر ابنتيه وتابعنا.
T remove() {
T x = a[0];
a[0] = a[--n];
trickleDown(0);
if (3*n < a.length) resize();
return x;
}
void trickleDown(int i) {
do {
int j = -1;
int r = right(i);
if (r < n && compare(a[r], a[i]) < 0) {
int l = left(i);
if (compare(a[l], a[r]) < 0) {
j = l;
} else {
j = r;
}
} else {
int l = left(i);
if (l < n && compare(a[l], a[i]) < 0) {
j = l;
}
}
if (j >= 0) swap(i, j);
i = j;
} while (i >= 0);
}
الشكل 10.3: إزالة أصغر قيمة، وهي 4، من BinaryHeap. 
ومثل سائر البنى المعتمدة على المصفوفات، سنتجاهل الزمن الذي يُنفق في استدعاءات ، إذ يمكن تبريره بحجّة التطفئة (amortization) الواردة في الملمة 2.1. ويفترق زمنا تشغيل و على ارتفاع الشجرة الثنائية (الضمنية). ومن حسن الحظ أنّ هذه شجرة ثنائية كاملة؛ فكل مستوى سوى الأخير فيه أكبر عدد ممكن من العقد. وعليه، إذا كان ارتفاع هذه الشجرة ، فإنّ فيها ما لا يقلّ عن عقدة. وبعبارة أخرى
وأخذ لوغاريتمات طرفي هذه المعادلة يعطي
وعليه، فإنّ عمليتَي و تعملان في زمن .
10.1.1 الخلاصة تلخّص المبرهنة التالية أداء بنية البيانات BinaryHeap: المبرهنة 10.1 *يطبّق BinaryHeap واجهة طابور (الأولوية). وتجاهلًا تكلفة استدعاءات ، يدعم BinaryHeap العمليتين و في زمن لكل عملية. * وفضلا عن ذلك، إذا بدأنا من BinaryHeap فارغ، فإنّ أي تسلسلٍ من عملية و يؤدّي إلى زمنٍ كلّي قدره مُنفق في جميع استدعاءات .
10.2 MeldableHeap: كومة قابلة للدمج عشوائية
الأقسام الفرعية
10.2 MeldableHeap: كومة قابلة للدمج عشوائية
نصف في هذا القسم بنية البيانات MeldableHeap، وهي تنفيذٌ لطابور الأولوية تكون فيه البنية الأساسية أيضًا شجرة ثنائية مرتّبة ترتيب كومة (heap-ordered). غير أنّه، بخلاف BinaryHeap الذي تُحدَّد فيه الشجرة الثنائية الأساسية تمامًا بعدد العناصر، لا توجد قيودٍ على شكل الشجرة الثنائية التي تقوم عليها بنية MeldableHeap؛ فأيّ شكلٍ يصاح. أمّا العمليتان و في MeldableHeap فتُنفَّذان بدلالة العملية . تأخذ هذه العملية عقدتَي كومة و وتدمجهما، وتُرجع عقدة كومةٍ تكون جذر كومةٍ تحتوي جميع العناصر في الشجرة الفرعية المجذَّرة عند وجميع العناصر في الشجرة الفرعية المجذَّرة عند . ومن مزايا العملية أنّه يمكن تعريفها على نحو تعاودي (recursive). انظر الشكل 10.4. فإذا كانت أو على القيمة ، فإنّنا ندمج مع مجموعةٍ فارغة، فنُرجع أو على التوالي. وإلّا، فافترض ، إذ إنّنا لو كان لاستطعنا تبديل دورَي و . وعندئذٍ نعرف أنّ جذر الكومة المدموجة سيحتوي ، ويمكننا أن ندمج تعاوديًا مع أو ، كيفما شئنا. وهنا يأتي دور العشوائية (randomization): فنقذف عملة (coin) لتقرّر ما إذا كنّا سندمج مع أم مع :
Node<T> merge(Node<T> h1, Node<T> h2) {
if (h1 == nil) return h2;
if (h2 == nil) return h1;
if (compare(h2.x, h1.x) < 0) return merge(h2, h1);
// now we know h1.x <= h2.x
if (rand.nextBoolean()) {
h1.left = merge(h1.left, h2);
h1.left.parent = h1;
} else {
h1.right = merge(h1.right, h2);
h1.right.parent = h1;
}
return h1;
}
نبيّن في القسم التالي أنّ تعمل في زمنٍ متوقَّع قدره ، حيث هو العدد الإجمالي للعناصر في و . ومع توفّر العملية تصير العملية سهلة. فننشئ عقدةً جديدة تحتوي ثمّ ندمج مع جذر كومتنا:
boolean add(T x) {
Node<T> u = newNode();
u.x = x;
r = merge(u, r);
r.parent = nil;
n++;
return true;
}
وهذا يستغرق زمنًا متوقَّعًا قدره . والعملية سهلةٌ على نحو مماثل. فالعقدة التي نريد إزالتها هي الجذر، لذا ندمج ابنتيها فحسب ونجعل الناتج هو الجذر:
T remove() {
T x = r.x;
r = merge(r.left, r.right);
if (r != nil) r.parent = nil;
n--;
return x;
}
ومرّةً أخرى، يستغرق هذا زمنًا متوقَّعًا قدره .
وفضلا عن ذلك، يمكن لـ MeldableHeap تنفيذ عملياتٍ كثيرة أخرى في زمنٍ متوقَّع قدره ، من بينها: : إزالة العقدة (ومفتاحها ) من الكومة. : إضافة جميع عناصر بنية MeldableHeap إلى هذه الكومة، وإفراغ في أثناء ذلك. ويمكن تنفيذ كلٍّ من هاتين العمليتين باستعمال عددٍ ثابت من عمليات ، كلٌّ منها يستغرق زمنًا متوقَّعًا قدره . 10.2.1 تحليل يستند تحليل إلى تحليل مسيرٍ عشوائي (random walk) في شجرة ثنائية. يبدأ المسير العشوائي في شجرة ثنائية من جذر الشجرة. وفي كل خطوةٍ من خطواته، تُقذف عملة، وبحسب نتيجة هذه الرمية يتقدّم المسير إلى الابنة اليسرى أو إلى الابنة اليمنى للعقدة الحالية. وينتهي المسير حين يسقط خارج الشجرة (تصير العقدة الحالية على القيمة ). والملمة التالية لافتةٌ إلى حدٍّ ما لأنّها لا تعتمد إطلاقًا على شكل الشجرة الثنائية: الملمة 10.1 الطول المتوقَّع لمسيرٍ عشوائي في شجرة ثنائية فيها عقدة هو على الأكثر .
البرهان. يتم البرهان بالاستدلال على . وفي الحالة الأساس، ويكون طول المسير . ولنفترض الآن أنّ النتيجة صحيحة لكل الأعداد الصحيحة غير السالبة .
ولنجعل يدلّ على حجم الشجرة الفرعية اليسرى للجذر، بحيث يكون حجم الشجرة الفرعية اليمنى للجذر. ومنطلقًا من الجذر، يأخذ المسير خطوةً واحدة ثمّ يتابع داخل شجرةٍ فرعية حجمها أو . وبموجب فرضية الاستدلال لدينا، يكون الطول المتوقَّع للمسير حينئذٍ
إذ إنّ كلٍّ من و أصغر من . وبما أنّ دالةً محدَّبة (concave)، فإنّ يبلغ قيمته العظمى عندما . وعليه، فإنّ عدد الخطوات المتوقَّع الذي يأخذه المسير العشوائي هو
ونستطرد استطرادًا قصيرًا لنلاحظ أنّه يمكن، لكل قارئٍ يعرف بعض نظرية المعلومات (information theory)، صياغة برهان الملمة 10.1 بدلالةِ إنتروبيا (entropy).
البرهان. [البرهان بالمعلوماتية للملمة 10.1] وليدلّ على عمق العقدة الخارجية رقم ، ولنتذكّر أنّ الشجرة الثنائية التي فيها عقدةً تضمّ عقدةً خارجية. واحتمال أن يبلغ المسير العشوائي العقدة الخارجية رقم هو بالضبط ، ومن ثمّ يُعطى الطول المتوقَّع للمسير العشوائي بالمعادلة
أمّا الطرف الأيمن من هذه المعادلة فيُعرف بسهولة على أنّه إنتروبيا (entropy) لتوزيعٍ احتمالي على عنصرًا. ومن الحقائق الأساسية حول إنتروبيا توزيعٍ على عنصرًا أنّها لا تتجاوز ، ممّا يُثبت الملمة.
ومع هذه النتيجة عن المسيرات العشوائية، يمكننا الآن بسهولة إثبات أنّ زمن تشغيل العملية هو . الملمة 10.2 إذا كانت و جذرَي كومتين تضمّان و عقدةً على التوالي، فإنّ زمن التشغيل المتوقَّع للعملية هو على الأكثر ، حيث .
البرهان. تأخذ كل خطوةٍ من خطوات خوارزمية الدمج خطوةً واحدة من مسيرٍ عشوائي، إمّا في الكومة المجذَّرة عند وإمّا في الكومة المجذَّرة عند . وتنتهي الخوارزمية عندما يسقط أحد هذين المسيرين العشوائيين خارج شجرته المقابلة (عندما أو ). وعليه، فإنّ عدد الخطوات المتوقَّع الذي تنفّذه خوارزمية الدمج هو على الأكثر
10.2.2 الخلاصة تلخّص المبرهنة التالية أداء بنية البيانات MeldableHeap: المبرهنة 10.2 يطبّق MeldableHeap واجهة طابور (الأولوية). ويدعم MeldableHeap العمليتين و في زمنٍ متوقَّع قدره لكل عملية.
10.3 مناقشة والتمارين
يبدو أنّ التمثيل الضمني للشجرة الثنائية الكاملة بوصفه مصفوفةً (أو قائمةً) أوّل ما اقترحه Eytzinger [27]. وقد استعمل هذا التمثيل في كتبٍ تحتوي على أشجار نسبية (pedigree) للعائلات النبيلة. وأما بنية البيانات BinaryHeap الموصوفة هنا فقد أدخلها أوّلًا Williams [78]. ويبدو أنّ بنية البيانات العشوائية MeldableHeap الموصوفة هنا أوّل ما اقترحها Gambin وMalinowski [34]. وهناك تنفيذاتٌ أخرى للكومات القابلة للدمج (meldable heaps)، منها الكومات اليسارية (leftist heaps) [16,48, القسم 5.3.2]، والكومات الثنائية (binomial heaps) [75]، وكومات فيبوناتشي (Fibonacci heaps) [30]، وكومات الأزواج (pairing heaps) [29]، والكومات المائلة (skew heaps) [72]، وإنّما لم يكن أيٌّ منها بسيطًا بقدر بنية MeldableHeap. وتدعم بعض البنى المذكورة أعلاه أيضًا عملية التي تُنقص فيها القيمة المخزَّنة عند العقدة إلى . (ويُشترط سلفًا أن يكون .) وفي معظم البنى السابقة، يمكن دعم هذه العملية في زمن بإزالة العقدة وإضافة . غير أنّ بعض هذه البنى يمكنها تنفيذ بكفاءةٍ أعلى. وتحديدًا، تستغرق زمنًا مُطفَّأ (amortized) قدره في كومات فيبوناتشي، وزمنًا مُطفَّأ قدره في نسخةٍ خاصة من كومات الأزواج [25]. ولهذه العملية الأكفأ تطبيقاتٌ في تسريع عدة خوارزميات رسمٍ بياني (graph)، ومنها خوارزمية أقصر مسار في Dijkstra [30]. التمرين 10.1 بيّن إضافة القيمة 7 ثمّ القيمة 3 إلى BinaryHeap المبيَّن في نهاية الشكل 10.2.
التمرين 10.2 بيّن إزالة القيّمين التاليين (6 و8) من BinaryHeap المبيَّن في نهاية الشكل 10.3.
التمرين 10.3 نفّذ الطريقة التي تزيل القيمة المخزَّنة في في BinaryHeap. وينبغي أن تعمل هذه الطريقة في زمن . ثمّ اشرح لماذا يُرجَّح ألّا تكون هذه الطريقة نافعة.
التمرين 10.4 الشجرة الـ -ary هي تعميمٌ للشجرة الثنائية، بحيث يكون لكل عقدةٍ داخلية ابنة. وباستعمال طريقة Eytzinger يمكن أيضًا تمثيل أشجار الـ -ary كاملة باستخدام المصفوفات. فاشتقّ المعادلات التي، معطى فهرس ، تحدّد فهرس الأمّ لـ وفهرس كلٍّ من ابنتَي الـ في هذا التمثيل.
التمرين 10.5 بالاعتماد على ما تعلّمته في التمرين 10.4، صمّم ونفّذ بنية DaryHeap، وهي التعميم الـ -ary لبنية BinaryHeap. وحلّل أزمنة تشغيل العمليات على DaryHeap، واختبر أداء تنفيذك لـ DaryHeap مقابل تنفيذ BinaryHeap المعطى هنا.
التمرين 10.6 بيّن إضافة القيمة 17 ثمّ القيمة 82 في MeldableHeap المبيَّنة في الشكل 10.4. واستعمل عملةً لمحاكاة بتٍ عشوائي عند الحاجة.
التمرين 10.7 بيّن إزالة القيّمين التاليين (4 و8) في MeldableHeap المبيَّنة في الشكل 10.4. واستعمل عملةً لمحاكاة بتٍ عشوائي عند الحاجة.
التمرين 10.8 نفّذ الطريقة التي تزيل العقدة من MeldableHeap. وينبغي أن تعمل هذه الطريقة في زمنٍ متوقَّع قدره .
التمرين 10.9 بيّن كيف يمكن العثور على ثاني أصغر قيمة في BinaryHeap أو MeldableHeap في زمنٍ ثابت.
التمرين 10.10 بيّن كيف يمكن العثور على أصغر قيمة في BinaryHeap أو MeldableHeap في زمن . (تلميح: قد يفيد استعمال كومة أخرى.)
التمرين 10.11 افترض أنّ لديك قوائم مرتَّبة، طولها الإجمالي . وباستعمال كومة، بيّن كيف يمكن دمجها في قائمةٍ مرتَّبة واحدة في زمن . (تلميح: قد يكون البدء بالحالة مفيدًا.)