مرجع
آخر الزيارات

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

406 كلمة•0 مشاهدة•🗒️ منذ 8 أيام
باختصار: يشير مصطلح الكومة في سياق بنى البيانات إلى شجرة بيانات كاملة لها خاصية الكومة، وهي خاصية ترتيب العُقد حسب مقارنة عقد الأبناء بعقدة الأب (عقدة الأصل)، بحيث تكون عقدة الأب أكبر من كل أبنائه إذا كانت كومة كبرى، أو أصغر من كل أبنائه إذا كانت…. في هذه المقالة 5 أقسام: «نكرر الخطوات السابقة على العُقدة التالية»، «تمثيل الكومة بمصفوفة حاسوبية» و«نكرر الخطوات السابقة على العُقدة التالية» وغيرها.
المحتويات
  1. نكرر الخطوات السابقة على العُقدة التالية
  2. تمثيل الكومة بمصفوفة حاسوبية
  3. نكرر الخطوات السابقة على العُقدة التالية
  4. نكرر الخطوات السابقة على العُقدة التالية
  5. خوارزمية تصنيفية
كومة (هياكل بيانات)

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

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

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

نكرر الخطوات السابقة على العُقدة التالية

العقدة اليسرى لها : توضع في عنصر المصفوفة الذي مؤشره

العقدة اليمنى لها : توضع في عنصر المصفوفة الذي مؤشره

تمثيل الكومة بمصفوفة حاسوبية

وعلى صعيد آخر، نبدأ بعقدة الجذر في الكومة (العقدة الأولى) فنضعها أقصى يسار المصفوفة (العنصر الذي مؤشره )، ثم نُطبق القانون العام على عقدة الجذر كما يلي:

من جهة ثانية، نحدد نوع الكومة بتحديد عدد العقد الفرعية لكل عقدة أصلية (هنا في المثال عقدتين فرعيتين فقط لكل عقدة أصلية فتكون الكومة هنا كومة ثنائية).

  • العقدة اليسرى: وتوضع في عنصر المصفوفة الذي مؤشره حيث مؤشر العقدة الأصلية
  • العقدة اليمنى: وتوضع في عنصر المصفوفة الذي مؤشره حيث مؤشر العقدة الأصلية
  • نكرر الخطوات السابقة حتى ننتهي من جميع العُقد التي لها عُقد فرعية (أبناء).
  • وبتطبيق الخطوات التالية على الكومة المقابلة يكون الناتج كما يلي:
  • لكل عقدة أصلية عقدتين فرعيتين، أي أن الكومة ثنائية
  • عقدة الجذر : توضع أقصى يسار المصفوفة (العنصر الذي مؤشره )
  • العقدة اليسرى لها : توضع في عنصر المصفوفة الذي مؤشره
  • العقدة اليمنى لها : توضع في عنصر المصفوفة الذي مؤشره

إضافةً إلى ذلك، عادة ما تُمثل الكومة بمصفوفة حاسوبية، وتُرتب عُقد الكومة على شكل عناصر في المصفوفة بحسب مؤشرها وطبقا للخطوات التالية:

نكرر الخطوات السابقة على العُقدة التالية

  • العقدة اليسرى لها : توضع في عنصر المصفوفة الذي مؤشره
  • العقدة اليمنى لها : توضع في عنصر المصفوفة الذي مؤشره
  • فتكون المصفوفة كما يلي:
  • انظر كذلك

نكرر الخطوات السابقة على العُقدة التالية

العقدة اليسرى لها : توضع في عنصر المصفوفة الذي مؤشره

العقدة اليمنى لها : توضع في عنصر المصفوفة الذي مؤشره

خوارزمية تصنيفية

المكدس (هياكل بيانات)

شجرة (هياكل بيانات)

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.