كومة ثنائية

تصغير|مثال على كومة ثنائية دقيقة كاملة.
الكومة الثنائية هي بنية بيانات كومة تتخذ شكل شجرة ثنائية. تُعد الكومات الثنائية طريقة شائعة لتنفيذ رتل الأولوية.  قدّم جون ويليامز الكومة الثنائية عام 1964 كبنية بيانات لتنفيذ فرز الكومة.

تُعرَّف الكومة الثنائية بأنها شجرة ثنائية ذات قيدين إضافيين:

 خاصية الشكل: الكومة الثنائية هي شجرة ثنائية كاملة؛ أي أن جميع مستويات الشجرة، باستثناء الأخير (الأعمق)، تكون ممتلئة بالكامل، وإذا لم يكن المستوى الأخير من الشجرة مكتملًا، تُملأ عقد ذلك المستوى من اليسار إلى اليمين.

 خاصية الكومة: المفتاح المخزن في كل عقدة يكون إما أكبر من أو يساوي (≥) أو أصغر من أو يساوي (≤) المفاتيح في العقد الأصغر، وفقًا لترتيب إجمالي معين.

 عمليات الكومة 
تُعدِّل كلٌّ من عمليتي الإدراج والإزالة الكومة للحفاظ على خاصية الشكل أولًا، وذلك بإضافة أو إزالة من نهايتها. ثم تُستعاد خاصية الكومة بالتنقل لأعلى أو لأسفل الكومة. تستغرق كلتا العمليتين وقتًا قدره O(log n).

 إدراج 
لإدراج عنصر في كومة، يُتبع الخطوات التالية:

 إضافة العنصر إلى المستوى السفلي من الكومة في أقصى اليسار.
 مقارنة العنصر المضاف بعنصره الأصلي؛ والتوثق في حال كان الترتيب صحيحًا.
 إذا لم يكن كذلك، يُبدل العنصر بعنصره الأصلي، ثم العودة مجدداً إلى الخطوة السابقة.
يعتمد عدد العمليات المطلوبة فقط على عدد المستويات التي يجب أن يصل إليها العنصر الجديد لتلبية خاصية الكومة. وبالتالي، فإن عملية الإدراج لها تعقيد زمني في أسوأ الحالات يساوي O(log n). في الكومة العشوائية، وفي عمليات الإدراج المتكررة، يكون متوسط تعقيد عملية الإدراج O(1).

 استخراج 
إجراء حذف الجذر من الكومة (استخراج العنصر الأقصى في الكومة القصوى أو العنصر الأدنى في الكومة الدنيا) مع الاحتفاظ بخاصية الكومة هو كما يلي:

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

 المراجع 

تصنيف:أشجار اثنانية