كومة ذات حدين

تعرف الكومة ذات الحدين في علوم الحاسوب بأنها كومة شبيهة بالكومة الثنائية إلا أنها تدعم إمكانية دمج كومتين مختلفتين مع بعضهما بشكل فعال، ويتم القيام بذلك عبر استخدام بنية معطيات شجرية خاصة. تعتبر الكومة ذات الحدين تحقيقاً هاماً لبنية المعطيات المجردة المسماة بالكومة القابلة للدمج، والتي تعرف بأنها رتلاً أفضلياً يدعم ميزة الدمج.

تحقيق الكومة

تُحقق الكومة ذات الحدين باستخدام مجموعة من الأشجار ذات الحدين. تعرف الشجرة ذات الحدين تعاودياً على الشكل التالي:

• الشجرة ذات الحدين ذات الرتبة 0 عبارة عن عقدة.
• الشجرة ذات الحدين ذات الرتبة k تمتلك عقدة جذر بحيث بكون أولاد هذه العقدة بدورهم جذوراً لأشجار ذات الحدين رتبها تتدرج على الشكل التالي: 0، 1، 2، ... k-1، k-2

تمتلك الشجرة ذات الحدين ذات الرتبة k عدداً من العقد مقداره 2^k وعمقاً مقداره k.

أشجار ذات حدين بالرتب 0 حتى 3: لدى كل شجرة عقدة جذر وأشجار فرعية من جميع الرتب الأخفض منها كما هو مشار. على سبيل المثال تتصل الشجرة ذات الحدين ذات الرتبة 3 بأشجار فرعية ذات الرتب 2 و1 و0 (ملونة بالأزرق والأخضر والأحمر على الترتيب).

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

انظر أيضًا

• الكومة (بنية معطيات)