كومة (هياكل بيانات)
يشير مصطلح الكومة في سياق هياكل البيانات إلى شجرة بيانات لها خاصية الكومة، وهي خاصية تشير ترتيب العثُعقد بعد مقارنة عقد الأبناء بعقدة الأب (عقدة الأصل) بحيث تكون عقدة الأب أكبر من كل أبنائه إذا كانت في الكومة كبرى، أو أصغر من كل أبنائه إذا كانت كومة صغرى، مع تجاهل ترتيب عُقد المستوى الواحد (انظر الشكل المقابل)، ونظرا لذلك فإنه لا يمكن إجراء مسح للكومة باستخدام البحث الثنائي.
يتباين عدد العقد الفرعية لكل عقدة أصلية حسب نوع الكومة، لكن الشكل الأكثر شيوعا هو الكومة التي تحتوي على عقدتين فرعيتين فقط لكل عقدة أصلية، وتسمى الكومة الثنائية، وفيها تكون شجرة البيانات شجرة ثنائية كاملة،[1] وتمثل هياكل بيانية لخوارزمية تصنيف الكومة.[2]
يمكن تمثيل الكومة تمثيلا خطيا في شكل مصفوفة حاسوبية، باستخدام قانون يربط بين أماكن العقد الأصلية والفرعية.
تعد الكومة ضرورية في العديد من خوارزميات الرسم البياني الفعالة مثل خوارزمية ديكسترا، وتُمثل أحد التطبيقات ذات الكفاءة القصوى لنوع من البيانات المجردة يسمى <i>طابور الأولوية</i>.
بناء الكومة[عدل]
عادة ما يتم بناء الكومة باستخدام المصفوفة الحاسوبية، حيث يُمثل كل عنصر في المصفوفة عقدة في الكومة، وتكون العلاقة بين العقد الأصلية والعقد الفرعية معروفة ضمنيا بالاعتماد على مؤشر العنصر في المصفوفة (الأرقام الصغيرة أسفل المصفوفة والمرتبة يسار من 0 وحتى 8).
لبناء الكومة الممثلة في المصفوفة الحاسوبية المقابلة نقوم بما يلي:
- نحدد عدد العقد الفرعية لكل عقدة أصلية (هنا في المثال عقدتين فرعيتين فقط لكل عقدة أصلية).
- نضع العنصر الموجود في أقصى يسار المصفوفة كعقدة الجذر في الكومة.
- نطبق القانون العام على كل عناصر المصفوفة ابتداء من اليسار:
- مؤشر العقدة اليسرى: (2i+1) حيث i مؤشر العقدة الأصلية
- مؤشر العقدة اليمنى: (2i+2) حيث i مؤشر العقدة الأصلية
فيكون الناتج كما يلي:
عنصر 100: هو عقدة الجذر، مؤشره (i=0)
- مؤشر العقدة اليسرى المتفرعة عنه: 1=(2*0+1)=(2i+1)، وقيمتها 19
- مؤشر العقدة اليمنى المتفرعة عنه: 2=(2*0+2)=(2i+2)، وقيمتها 36
عنصر 19: مؤشره (i=1)
- مؤشر العقدة اليسرى المتفرعة عنه: 3=(2*1+1)=(2i+1)، وقيمتها 17
- مؤشر العقدة اليمنى المتفرعة عنه: 5=(2*1+2)=(2i+2)، وقيمتها 3
وهكذا حتى نهاية المصفوفة.
انظر أيضا[عدل]
مصادر[عدل]
- ^ CORMEN، THOMAS H. (2009). INTRODUCTION TO ALGORITHMS. United States of America: The MIT Press Cambridge, Massachusetts London, England. ص. 151–152. ISBN:978-0-262-03384-8.
- ^ Williams، J. W. J. (1964)، "Algorithm 232 - Heapsort"، Communications of the ACM، ج. 7، ص. 347–348، DOI:10.1145/512274.512284
| كومة في المشاريع الشقيقة: | |
| |
| كومة في المشاريع الشقيقة: | |
| |