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

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

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

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

انظر أيضاً

مراجع
  1. heapq.heappush نسخة محفوظة 04 ديسمبر 2017 على موقع واي باك مشين.
  2. Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF), 104, Academic Press, صفحات 197–214, doi:10.1006/inco.1993.1030, مؤرشف من الأصل (PDF) في 3 ديسمبر 2012 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
  3. Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7, صفحات 347–348, doi:10.1145/512274.512284 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
    • بوابة برمجة الحاسوب
    • بوابة علم الحاسوب
    في كومنز صور وملفات عن: الكومة
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.