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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
مثال على كومة ثنائية كاملة عظمى تتراوح فيها قيم مفاتيح العقد بين 1 و100.

تعرف الكومة (أو الكدسة) (بالإنجليزية: Heap) في علوم الحاسوب بأنها بنية معطيات شجرية تتمتع بصفة خاصة وهي تحقيق عناصرها لخاصية الكومة (بالإنجليزية: Heap Property) : إذا كانت العقدة A أباً للعقدة B عندئذ يكون مفتاح العقدة A مرتباً بالنسبة لمفتاح العقدة B حسب أسلوب الترتيب المتبع في الكومة.[1][2][3] إما أن تكون مفاتيح العقد الآباء أكبر من مفاتيح الأبناء بحيث يحمل مفتاح عقدة الجذر القيمة الأعظمية (تسمى الكومة في هذه الحالة كومة عظمى) أو تكون مفاتيح العقد الآباء أصغر من مفاتيح العقد الأبناء بحيث يحمل مفتاح عقدة الجذر القيمة الأصغرية (كومة صغرى).

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

انظر أيضاً[عدل]

مراجع[عدل]

  1. ^ heapq.heappush نسخة محفوظة 04 ديسمبر 2017 على موقع واي باك مشين.
  2. ^ Frederickson، Greg N. (1993)، "An Optimal Algorithm for Selection in a Min-Heap"، Information and Computation (PDF)، 104 (2)، Academic Press، صفحات 197–214، doi:10.1006/inco.1993.1030 
  3. ^ Williams، J. W. J. (1964)، "Algorithm 232 - Heapsort"، Communications of the ACM، 7 (6): 347–348، doi:10.1145/512274.512284 
Computer.svg
هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال بحاجة للتوسيع. شارك في تحريرها.