ملخص

مراجعة النقاط الرئيسية

• الكومة شجرة ثنائية كاملة. ووفقاً للخاصية التي تحققها يمكن تصنيفها إلى كومة عظمى أو كومة صغرى. والعنصر الأعلى في الكومة العظمى (الصغرى) هو العنصر الأكبر (الأصغر).
• طابور الأولوية طابور تُسحب عناصره وفق الأولوية، ويُنفَّذ عادةً باستخدام كومة.
• تشمل عمليات الكومة الشائعة وتعقيداتها الزمنية المقابلة: إدراج عنصر $O(\log n)$، وحذف العنصر الأعلى $O(\log n)$، والوصول إلى العنصر الأعلى $O(1)$.
• تُلائم الأشجار الثنائية الكاملة التمثيل بالمصفوفات، لذا نستخدم عادةً المصفوفات لتخزين الأكوام.
• تُستخدم عمليات تعديل الكومة للحفاظ على خاصية الكومة، وتُوظَّف في كل من عمليتي إدراج العناصر وحذفها.
• يمكن تحسين بناء كومة انطلاقاً من $n$ من عناصر الإدخال ليصبح $O(n)$، وهو أمر عالي الكفاءة.
• مسألة أعلى k مسألة خوارزمية كلاسيكية يمكن حلها بكفاءة باستخدام كومة، بتعقيد زمني $O(n \log k)$.

أسئلة وأجوبة

س: هل يعني مصطلح «الكومة» في بنى البيانات الشيء نفسه الذي يعنيه «heap» في إدارة الذاكرة؟

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