كومة ثنائية
الكومة الثنائية هي بنية بيانات كومة تتخذ شكل شجرة ثنائية. تُعد الكومات الثنائية طريقة شائعة لتنفيذ رتل الأولوية.[1] قدّم جون ويليامزجون ويليمز الكومة الثنائية عام 1964 كبنية بيانات لتنفيذ فرز الكومة.
تُعرَّف الكومة الثنائية بأنها شجرة ثنائية ذات قيدين إضافيين:[2]
- خاصية الشكل: الكومة الثنائية هي شجرة ثنائية كاملة؛ أي أن جميع مستويات الشجرة، باستثناء الأخير (الأعمق)، تكون ممتلئة بالكامل، وإذا لم يكن المستوى الأخير من الشجرة مكتملًا، تُملأ عقد ذلك المستوى من اليسار إلى اليمين.
- خاصية الكومة: المفتاح المخزن في كل عقدة يكون إما أكبر من أو يساوي (≥) أو أصغر من أو يساوي (≤) المفاتيح في العقد الأصغر، وفقًا لترتيب إجمالي معين.
عمليات الكومة
تُعدِّل كلٌّ من عمليتي الإدراج والإزالة الكومة للحفاظ على خاصية الشكل أولًا، وذلك بإضافة أو إزالة من نهايتها. ثم تُستعاد خاصية الكومة بالتنقل لأعلى أو لأسفل الكومة. تستغرق كلتا العمليتين وقتًا قدره O(log n).
إدراج
لإدراج عنصر في كومة، يُتبع الخطوات التالية:
- إضافة العنصر إلى المستوى السفلي من الكومة في أقصى اليسار.
- مقارنة العنصر المضاف بعنصره الأصلي؛ والتوثق في حال كان الترتيب صحيحًا.
- إذا لم يكن كذلك، يُبدل العنصر بعنصره الأصلي، ثم العودة مجدداً إلى الخطوة السابقة.
يعتمد عدد العمليات المطلوبة فقط على عدد المستويات التي يجب أن يصل إليها العنصر الجديد لتلبية خاصية الكومة. وبالتالي، فإن عملية الإدراج لها تعقيد زمني في أسوأ الحالات يساوي O(log n). في الكومة العشوائية، وفي عمليات الإدراج المتكررة، يكون متوسط تعقيد عملية الإدراج O(1).[3][4]
استخراج
إجراء حذف الجذر من الكومة (استخراج العنصر الأقصى في الكومة القصوى أو العنصر الأدنى في الكومة الدنيا) مع الاحتفاظ بخاصية الكومة هو كما يلي:
- استبدال جذر الكومة بالعنصر الأخير في المستوى الأخير.
- مفارنة الجذر الجديد بعناصره الفرعية؛ التوقف في حال كانت بالترتيب الصحيح.
- إذا لم يكن كذلك، تبديل العنصر بأحد عناصره الفرعية، ثم العودة إلى الخطوة السابقة.
المراجع
- ↑ رونالد ريفست، توماس كورمن، تشارلز لايسيرسين (1990). مقدمة في الخوارزميات.
{{استشهاد بكتاب}}: صيانة الاستشهاد: التاريخ والسنة (link) - ↑ Y Narahari، "Binary Heaps"، Data Structures and Algorithms، مؤرشف من الأصل في 2024-01-12
- ↑ Mehlhorn, Kurt; Tsakalidis, A. (Feb 1989). "Data structures". Universität des Saarlandes (بالإنجليزية): 27. DOI:10.22028/D291-26123. Archived from the original on 2024-08-29.
Porter and Simon [171] analyzed the average cost of inserting a random element into a random heap in terms of exchanges. They proved that this average is bounded by the constant 1.61. Their proof docs not generalize to sequences of insertions since random insertions into random heaps do not create random heaps. The repeated insertion problem was solved by Bollobas and Simon [27]; they show that the expected number of exchanges is bounded by 1.7645. The worst-case cost of inserts and deletemins was studied by Gonnet and Munro [84]; they give log log n + O(1) and log n + log n* + O(1) bounds for the number of comparisons respectively.
- ↑ Porter، Thomas؛ Simon، Istvan (سبتمبر 1975). "Random insertion into a priority queue structure". IEEE Transactions on Software Engineering. ج. SE-1 ع. 3: 292–298. DOI:10.1109/TSE.1975.6312854. ISSN:1939-3520. S2CID:18907513.
| الأنماط |
|
|---|---|
| مجردة |
|
| مصفوفية |
|
| مترابطة |
|
| شجرية |
|
| بيانية |
|
| |
