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

مثال على كومة ثنائية كاملة عظمى تتراوح فيها قيم مفاتيح العقد بين 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)، Academic Press، ج. 104، ص. 197–214، DOI:10.1006/inco.1993.1030، مؤرشف من الأصل (PDF) في 2012-12-03
3. Williams، J. W. J. (1964)، "Algorithm 232 - Heapsort"، Communications of the ACM، ج. 7، ص. 347–348، DOI:10.1145/512274.512284