بيب

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

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

تم تقديم نظام البيانات "beap" بواسطة إيان مونرو وهندرا سوواندا . ومن هياكل البيانات ذات الصلة نظام " Young Tableau" .

يبلغ ارتفاع الهيكل تقريبًا${\displaystyle {\sqrt {n}}}$. كذلك، بافتراض أن المستوى الأخير ممتلئ، فإن عدد العناصر في ذلك المستوى هو أيضًا${\displaystyle {\sqrt {n}}}$في الواقع، وبسبب هذه الخصائص، يتم تنفيذ جميع العمليات الأساسية (الإدراج، والحذف، والبحث) في${\displaystyle O({\sqrt {n}})}$متوسط ​​الوقت. يمكن أن تكون عمليات البحث في الكومة${\displaystyle O(n)}$في أسوأ الأحوال، تتضمن إزالة العناصر وإدخال عناصر جديدة نشر العناصر لأعلى أو لأسفل (كما هو الحال في الكومة) لاستعادة ثبات الكومة. ومن المزايا الإضافية أن الكومة توفر وصولاً ثابتاً إلى أصغر عنصر.${\displaystyle O({\sqrt {n}})}$الوقت اللازم لأقصى عنصر.

في الواقع، أ${\displaystyle O({\sqrt {n}})}$يمكن تنفيذ عملية البحث إذا تم الاحتفاظ بمؤشرات الأصل عند كل عقدة. ستبدأ من العنصر السفلي المطلق للعقدة العلوية (على غرار الابن الأيسر في كومة) وتتحرك إما لأعلى أو لليمين للعثور على العنصر المطلوب.

• مونرو، ج. إيان؛ سواندا، هندرا (1980). "هياكل البيانات الضمنية للبحث والتحديث السريع" . مجلة علوم الحاسوب والنظم . 21 (2): 236-250 . doi : 10.1016/0022-0000(80)90037-9 .
• ويليامز، جيه دبليو جيه (يونيو 1964). "الخوارزمية 232 - فرز الكومة". اتصالات رابطة آلات الحوسبة . 7 (6): 347-348 . doi : 10.1145/512274.512284 .