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

خوارزمية لتنفيذ خاصية الكومة على شجرة ثلاثية

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

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

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

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

[عدل]
كومة كبري وتمثيلها بمصفوفة حاسوبية

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

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

وبتطبيق الخطوات التالية على الكومة المقابلة يكون الناتج كما يلي:

  • لكل عقدة أصلية عقدتين فرعيتين، أي أن الكومة ثنائية
  • عقدة الجذر 100: توضع أقصى يسار المصفوفة (العنصر الذي مؤشره (i=0))
    • العقدة اليسرى لها 19: توضع في عنصر المصفوفة الذي مؤشره 1=(2*0+1)=(2i+1)
    • العقدة اليمنى لها 36: توضع في عنصر المصفوفة الذي مؤشره 2=(2*0+2)=(2i+2)
  • نكرر الخطوات السابقة على العُقدة التالية 19
    • العقدة اليسرى لها 17: توضع في عنصر المصفوفة الذي مؤشره 3=(2*1+1)=(2i+1)
    • العقدة اليمنى لها 3: توضع في عنصر المصفوفة الذي مؤشره 4=(2*1+2)=(2i+2)
  • نكرر الخطوات السابقة على العُقدة التالية 36
    • العقدة اليسرى لها 25: توضع في عنصر المصفوفة الذي مؤشره 5=(2*2+1)=(2i+1)
    • العقدة اليمنى لها 1: توضع في عنصر المصفوفة الذي مؤشره 6=(2*2+2)=(2i+2)
  • نكرر الخطوات السابقة على العُقدة التالية 17
    • العقدة اليسرى لها 2: توضع في عنصر المصفوفة الذي مؤشره 7=(2*3+1)=(2i+1)
    • العقدة اليمنى لها 7: توضع في عنصر المصفوفة الذي مؤشره 8=(2*3+2)=(2i+2)

فتكون المصفوفة كما يلي:

7 2 1 25 3 17 36 19 100

انظر أيضا

[عدل]

مصادر

[عدل]
  1. ^ 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.
  2. ^ Williams، J. W. J. (1964)، "Algorithm 232 - Heapsort"، Communications of the ACM، ج. 7، ص. 347–348، DOI:10.1145/512274.512284