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

تشبية لكومة البيانات. شكل 1: يمثل كومة كبرى، فابتداءا من رأس الكومة التي تأخذ أكبر قيمة، فإن كل مستوي عرَضي تقل قيم جميع عقده عن قيم عقد المستوى الذي يسبقه.
شكل 2: يمثل كومة صغرى، فابتداءا من رأس الكومة التي تأخذ أقل قيمة، فإن كل مستوي عرَضي تزيد قيم جميع عقده عن قيم عقد المستوى الذي يسبقه.
مع ملاحظة عدم أهمية الترتيب بين عقد المستوى الواحد.

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

يتباين عدد العقد الفرعية لكل عقدة أصلية حسب نوع الكومة، لكن الشكل الأكثر شيوعا هو الكومة التي تحتوي على عقدتين فرعيتين فقط لكل عقدة أصلية، وتسمى الكومة الثنائية، وفيها تكون شجرة البيانات شجرة ثنائية كاملة، وتمثل هياكل بيانية لخوارزمية تصنيف الكومة.

يمكن تمثيل الكومة تمثيلا خطيا في شكل مصفوفة حاسوبية، باستخدام قانون يربط بين أماكن العقد الأصلية والفرعية.

تعد الكومة ضرورية في العديد من خوارزميات الرسم البياني الفعالة مثل خوارزمية ديكسترا، وتُمثل أحد التطبيقات ذات الكفاءة القصوى لنوع من البيانات المجردة يسمى <i>طابور الأولوية</i>.

بناء الكومة

كومة كبري وطريقة تمثيل المصفوفة الحاسوبية لها.

عادة ما يتم بناء الكومة باستخدام المصفوفة الحاسوبية، حيث يُمثل كل عنصر في المصفوفة عقدة في الكومة، وتكون العلاقة بين العقد الأصلية والعقد الفرعية معروفة ضمنيا بالاعتماد على مؤشر العنصر في المصفوفة (الأرقام الصغيرة أسفل المصفوفة والمرتبة يسار من 0 وحتى 8).

لبناء الكومة الممثلة في المصفوفة الحاسوبية المقابلة نقوم بما يلي:

1. نحدد عدد العقد الفرعية لكل عقدة أصلية (هنا في المثال عقدتين فرعيتين فقط لكل عقدة أصلية).
2. نضع العنصر الموجود في أقصى يسار المصفوفة كعقدة الجذر في الكومة.
3. نطبق القانون العام على كل عناصر المصفوفة ابتداء من اليسار:
   1. مؤشر العقدة اليسرى: (2i+1) حيث i مؤشر العقدة الأصلية
   2. مؤشر العقدة اليمنى: (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

وهكذا حتى نهاية المصفوفة.

انظر أيضا

• خوارزمية تصنيفية
• المكدس (هياكل بيانات)
• شجرة (هياكل بيانات)