كومة ثنائية

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 40 صور
الموسوعة الحرة
مثال على كومة ثنائية كاملة ذات قيمة عظمى
مثال على كومة ثنائية دنيا كاملة

الكومة الثنائية هي بنية بيانات كومة تأخذ شكل شجرة ثنائية . تُعد الكومات الثنائية طريقة شائعة لتنفيذ قوائم الانتظار ذات الأولوية . [ 1 ] : 162-163. وقد قدم جيه دبليو جيه ويليامز الكومة الثنائية في عام 1964 كبنية بيانات لتنفيذ فرز الكومة . [ 2 ]

يتم تعريف الكومة الثنائية على أنها شجرة ثنائية مع قيدين إضافيين: [ 3 ]

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

تُسمى الأكوام التي يكون فيها مفتاح الأصل أكبر من أو يساوي (≥) مفاتيح الأبناء أكوامًا قصوى ؛ أما تلك التي يكون فيها أصغر من أو يساوي (≤) فتُسمى أكوامًا دنيا . توجد خوارزميات فعّالة (أي ذات زمن لوغاريتمي ) للعمليتين اللازمتين لتنفيذ طابور أولوية على كومة ثنائية.

  • إدراج عنصر؛
  • إزالة أصغر عنصر أو أكبر عنصر من (على التوالي) كومة دنيا أو كومة قصوى.

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

عمليات الكومة

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

أدخل

لإدراج عنصر في كومة، نقوم بالخطوات التالية:

  1. أضف العنصر إلى المستوى السفلي من الكومة في أقصى مساحة مفتوحة على اليسار.
  2. قارن العنصر المضاف بالعنصر الأصل؛ إذا كانا بالترتيب الصحيح، فتوقف.
  3. وإلا، فقم بتبديل العنصر مع العنصر الأصل وارجع إلى الخطوة السابقة.

تُسمى الخطوتان 2 و 3، اللتان تعملان على استعادة خاصية الكومة عن طريق مقارنة العقدة مع عقدتها الأصلية وربما تبديلها، بعملية الكومة الصاعدة (المعروفة أيضًا باسم bubble-up أو percolate-up أو sift-up أو trickle-up أو swim-up أو heapify-up أو cascade-up أو fix-up ).

يعتمد عدد العمليات المطلوبة فقط على عدد المستويات التي يجب أن يرتفع إليها العنصر الجديد لتحقيق خاصية الكومة. وبالتالي، فإن عملية الإضافة لها تعقيد زمني في أسوأ الحالات من رتبة O(log n ) . بالنسبة لكومة عشوائية، ولعمليات الإضافة المتكررة، فإن عملية الإضافة لها تعقيد زمني في الحالة المتوسطة من رتبة O(1). [ 4 ] [ 5 ]

رسم متحرك قصير يصور إضافة قيمة إلى كومة ثنائية قصوى.

يُظهر الرسم المتحرك التالي مثالًا على إدخال عنصر في كومة ثنائية. يبدأ بإدخال العدد 15 في الكومة عند المدخل الفارغ الأيسر في الصف التالي المتاح. مع ذلك، فإن خاصية الكومة غير محققة لأن 15 > 8 ، لذا نحتاج إلى تبديل العددين 15 و8. حتى بعد هذا التبديل، لا تزال خاصية الكومة غير محققة لأن 15 > 11 ، لذا نحتاج إلى التبديل مرة أخرى. الآن، خاصية الكومة محققة، وبالتالي فإن الشجرة الثنائية الناتجة هي كومة عظمى صالحة. لا حاجة للتحقق من الابن الأيسر بعد هذه الخطوة الأخيرة: في البداية، كانت الكومة العظمى صالحة، أي أن الجذر كان أكبر من ابنه الأيسر، لذا فإن استبدال الجذر بقيمة أكبر سيحافظ على خاصية أن كل عقدة أكبر من أبنائها ( 11 > 5 ؛ إذا كان 15 > 11 ، و 11 > 5 ، فإن 15 > 5 ، بسبب علاقة التعدي ).

يستخرج

تتمثل إجراءات حذف الجذر من الكومة (أي استخراج العنصر الأقصى في كومة الحد الأقصى أو العنصر الأدنى في كومة الحد الأدنى) مع الاحتفاظ بخاصية الكومة فيما يلي:

  1. استبدل جذر الكومة بالعنصر الأخير في المستوى الأخير.
  2. قارن الجذر الجديد بأبنائه؛ إذا كانوا بالترتيب الصحيح، فتوقف.
  3. وإلا، فقم بتبديل العنصر مع أحد أبنائه ثم عد إلى الخطوة السابقة. (بدّل مع ابنه الأصغر في كومة دنيا ومع ابنه الأكبر في كومة عظمى).

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

رسم متحرك قصير يصور استخراج قيمة من كومة ثنائية قصوى.

إذا كان لدينا نفس كومة العناصر القصوى كما في السابق، فإننا نزيل العدد 11 ونستبدله بالعدد 4. الآن، تُنتهك خاصية الكومة لأن العدد 8 أكبر من العدد 4. في هذه الحالة، يكفي تبديل العنصرين 4 و8 لاستعادة خاصية الكومة، ولا نحتاج إلى تبديل العناصر أكثر من ذلك.

في كومة الحد الأقصى، يتم تبديل العقدة المتحركة للأسفل مع أكبر أبنائها (أما في كومة الحد الأدنى، فتُبدَّل مع أصغر أبنائها)، حتى تُحقق خاصية الكومة في موقعها الجديد. تُنفَّذ هذه الوظيفة بواسطة دالة Max-Heapify كما هو مُعرَّف أدناه في الشفرة الزائفة لكومة مدعومة بمصفوفة A طولها length ( A ). يبدأ ترقيم عناصر A من 1.

// تنفيذ عملية تقليص حجم الكومة أو عملية تحويل الكومة إلى كومة تنازلية للكومة القصوى // A : مصفوفة تمثل الكومة، مفهرسة بدءًا من 1 // i : فهرس البداية عند إنشاء كومة تنازلية Max-Heapify ( A , i ): يسار ← 2× i يمين ← 2× i + 1 أكبر ← iإذا كان طول العنصر الأيسر أقل من أو يساوي طول المصفوفة A ، وكان العنصر الأيسر أكبر من العنصر الأكبر ، فإن العنصر الأكبر يُنقل إلى العنصر الأيسر. وإذا كان طول العنصر الأيمن أقل من أو يساوي طول المصفوفة A ، وكان العنصر الأيمن أكبر من العنصر الأكبر ، فإن العنصر الأكبر يُنقل إلى العنصر الأيمن.إذا كان الأكبر لا يساوي i ، فقم بما يلي : بدّل A [ i ] و A [ الأكبر ]، ثم قم بتطبيق طريقة Max-Heapify ( A , الأكبر ).

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

في أسوأ الحالات، يجب تبديل الجذر الجديد مع ابنه في كل مستوى حتى يصل إلى المستوى السفلي من الكومة، مما يعني أن عملية الحذف لها تعقيد زمني نسبي لارتفاع الشجرة، أو O(log n ).

أدخل ثم استخرج

يمكن إجراء عملية إدراج عنصر ثم استخراجه من الكومة بكفاءة أكبر من مجرد استدعاء دالتي الإدراج والاستخراج المذكورتين أعلاه، واللتين تتطلبان عمليتي إدراج واستخراج upheap. downheapبدلاً من ذلك، يمكننا إجراء downheapعملية واحدة فقط، كما يلي:

  1. قارن ما إذا كان العنصر الذي ندفعه أو العنصر الذي تم الوصول إليه من أعلى الكومة أكبر (بافتراض وجود كومة قصوى).
  2. إذا كان جذر الكومة أكبر:
    1. استبدل العنصر الجذر بالعنصر الجديد
    2. قم بتخفيض حجم الكومة بدءًا من الجذر
  3. وإلا، فأعد العنصر الذي نقوم بدفعه

توفر لغة بايثون دالةً لإضافة العناصر ثم استخراجها تُسمى "heappushpop"، والتي سنعيد صياغتها أدناه. [ 6 ] [ 7 ] يُفترض أن يكون العنصر الأول في مصفوفة الكومة عند الفهرس 1.

// دفع عنصر جديد إلى كومة (الحد الأقصى) ثم استخراج جذر الكومة الناتجة. // الكومة : مصفوفة تمثل الكومة، مفهرسة عند 1 // العنصر : عنصر لإدراجه // تُعيد القيمة الأكبر بين العنصر وجذر الكومة . Push-Pop ( heap : List<T>, item : T) -> T: if heap is not empty and heap[1] > item then : // < if min heap swap heap [1] and item _downheap( heap starting from index 1) return item

يمكن تعريف دالة مماثلة لحذف العناصر ثم إدراجها، وهو ما يسمى في بايثون "heapreplace":

// استخرج جذر الكومة، وأضف عنصرًا جديدًا // الكومة : مصفوفة تمثل الكومة، مفهرسة عند 1 // العنصر : عنصر لإدراجه // تُعيد الجذر الحالي للكومة. استبدال ( الكومة : قائمة<T>، العنصر : T) -> T: تبديل الكومة [1] والعنصر. _downheap( الكومة تبدأ من الفهرس 1) تُعيد العنصر.

يستغرق إيجاد عنصر عشوائي وقتًا قدره O(n).

يمكن إثبات ذلك بسهولة من خلال اعتبار أن الكومة غير مرتبة، لذلك نحتاج إلى البحث في الشجرة بأكملها للعثور على العنصر المستهدف.

يمسح

يمكن حذف عنصر عشوائي على النحو التالي:

  1. ابحث عن الفهرسأنا{\displaystyle i}العنصر الذي نريد حذفه
  2. بدّل هذا العنصر مع العنصر الأخير. ثم احذف العنصر الأخير بعد عملية التبديل.
  3. استخدم دالة down-heapify أو up-heapify لاستعادة خاصية الكومة. في كومة max-heap (min-heap)، لا يلزم استخدام up-heapify إلا عندما يكون المفتاح الجديد للعنصرأنا{\displaystyle i}أكبر (أصغر) من القيمة السابقة لأن خاصية الكومة للعنصر الأب فقط هي التي قد تُنتهك. بافتراض أن خاصية الكومة كانت صالحة بين العنصرينأنا{\displaystyle i}قبل تبديل العناصر، لا يمكن انتهاك خاصية الكومة بقيمة مفتاح أكبر (أصغر) جديدة. عندما يكون المفتاح الجديد أصغر (أكبر) من المفتاح السابق، يلزم فقط إجراء عملية تنازلية للكومة، لأن خاصية الكومة قد تُنتهك فقط في العناصر الفرعية.

تقليل أو زيادة المفتاح

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

يمكن إجراء عملية تقليل المفتاح على النحو التالي:

  1. ابحث عن فهرس العنصر الذي نريد تعديله
  2. قلل قيمة العقدة
  3. استخدم دالة Down-heapify (بافتراض وجود كومة قصوى) لاستعادة خاصية الكومة.

يمكن زيادة قيمة المفتاح كما يلي:

  1. ابحث عن فهرس العنصر الذي نريد تعديله
  2. قم بزيادة قيمة العقدة
  3. استخدم Up-heapify (بافتراض وجود كومة قصوى) لاستعادة خاصية الكومة

بناء كومة

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

مع ذلك، فإن طريقة ويليامز ليست مثالية. ثمة طريقة أسرع (بفضل فلويد [ 8 ] ) تبدأ بوضع العناصر عشوائيًا على شجرة ثنائية، مع مراعاة خاصية الشكل (يمكن تمثيل الشجرة بمصفوفة، انظر أدناه). ثم بدءًا من المستوى الأدنى والتحرك صعودًا، يتم فرز جذر كل شجرة فرعية نزولًا كما في خوارزمية الحذف حتى يتم استعادة خاصية الكومة. وبشكل أكثر تحديدًا، إذا كانت جميع الأشجار الفرعية تبدأ من ارتفاع معينح{\displaystyle h}تم بالفعل "تكديسها" (المستوى السفلي المقابل لـح=0{\displaystyle h=0}الأشجار على ارتفاعح+1{\displaystyle h+1}يمكن تحويل العناصر إلى كومة عن طريق إرسال جذرها لأسفل على طول مسار الأبناء ذوي القيمة القصوى عند بناء كومة قصوى، أو الأبناء ذوي القيمة الدنيا عند بناء كومة دنيا. تستغرق هذه العمليةيا(ح){\displaystyle O(h)}عدد العمليات (التبديلات) لكل عقدة. في هذه الطريقة، تحدث معظم عملية تكوين الكومة في المستويات الدنيا. نظرًا لأن ارتفاع الكومة هو⌊سجل⁡ن⌋{\displaystyle \lfloor \log n\rfloor }عدد العقد عند الارتفاعح{\displaystyle h}يكون≤2⌊سجل⁡ن⌋2ح≤ن2ح{\displaystyle \leq {\frac {2^{\lfloor \log n\rfloor }}{2^{h}}}\leq {\frac {n}{2^{h}}}}وبالتالي، فإن تكلفة تحويل جميع الأشجار الفرعية إلى كومة هي:

∑ح=0⌊سجل⁡ن⌋ن2حيا(ح)=يا(ن∑ح=0⌊سجل⁡ن⌋ح2ح)=يا(ن∑ح=0∞ح2ح)=يا(ن){\displaystyle {\begin{aligned}\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {n}{2^{h}}}O(h)&=O\left(n\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {h}{2^{h}}}\right)\\&=O\left(n\sum _{h=0}^{\infty }{\frac {h}{2^{h}}}\right)\\&=O(n)\end{aligned}}}

يعتمد هذا على حقيقة أن المتسلسلة اللانهائية المعطاة∑أنا=0∞أنا/2أنا{\textstyle \sum _{i=0}^{\infty }i/2^{i}}يتقارب .

من المعروف أن القيمة الدقيقة لما سبق (أسوأ عدد للمقارنات أثناء إنشاء الكومة) تساوي:

2ن-2s2(ن)-هـ2(ن){\displaystyle 2n-2s_{2}(n)-e_{2}(n)}، [ 9 ] [ ب ]

حيث s 2 ( n ) هو مجموع جميع أرقام التمثيل الثنائي لـ n و e 2 ( n ) هو أس 2 في التحليل الأولي لـ n .

يُعد تحليل الحالة المتوسطة أكثر تعقيدًا، ولكن يمكن إثبات أنها تقترب تقاربًا من 1.8814  مقارنة من n − 2 log 2 n + O (1) . [ 10 ] [ 11 ]

تقوم الدالة Build-Max-Heap، الموضحة أدناه، بتحويل المصفوفة A ، التي تخزن شجرة ثنائية كاملة مكونة من n عقدة، إلى كومة عظمى (max-heap) من خلال استخدام Max-Heapify (down-heapify للكومة العظمى) بشكل متكرر من الأسفل إلى الأعلى. عناصر المصفوفة المفهرسة بـ floor ( n /2) + 1 ، floor ( n /2) + 2 ، ...، n ، هي جميعها أوراق للشجرة (بافتراض أن الفهارس تبدأ من 1) - وبالتالي، كل منها عبارة عن كومة مكونة من عنصر واحد، ولا تحتاج إلى تحويلها إلى كومة تنازلية. تقوم الدالة Build-Max-Heap بتشغيل Max-Heapify على كل عقدة من عقد الشجرة المتبقية.

بناء كومة قصوى ( A ): لكل فهرس i من الجزء السفلي ( طول ( A )/2) إلى 1 ، قم بما يلي: تحويل إلى كومة قصوى ( A ، i )

تنفيذ الكومة

شجرة ثنائية كاملة صغيرة مخزنة في مصفوفة
مقارنة بين تنفيذ الكومة الثنائية وتنفيذ المصفوفة.

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

ليكن n عدد العناصر في الكومة، وليكن i فهرسًا صالحًا عشوائيًا للمصفوفة التي تخزن الكومة. إذا كان جذر الشجرة عند الفهرس 0، مع الفهارس الصالحة من 0 إلى n - 1، فإن كل عنصر a عند الفهرس i يكون

  • الأطفال عند المؤشرين 2i + 1 و 2i + 2
  • الأصل عند مستوى الفهرس (( i − 1) / 2).

أو بدلاً من ذلك، إذا كان جذر الشجرة عند الفهرس 1، مع وجود فهارس صالحة من 1 إلى n ، فإن كل عنصر a عند الفهرس i يحتوي على

  • الأطفال عند المؤشرين 2i و 2i + 1
  • الأصل عند مستوى الفهرس ( i / 2).

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

يمكن التعبير عن عمليات upheap"أو" downheapبدلالة مصفوفة كما يلي: لنفترض أن خاصية الكومة صحيحة للفهارس b ، b +1، ...، e . تعمل دالة "التصفية التنازلية" على توسيع خاصية الكومة لتشمل b -1، b ، b +1، ...، e . الفهرس i = b -1 هو الوحيد الذي قد يخالف خاصية الكومة. ليكن j فهرس أكبر عنصر فرعي لـ a[i] (للكومة العظمى، أو أصغر عنصر فرعي للكومة الصغرى) ضمن النطاق b، ...، e. (إذا لم يكن هناك فهرس كهذا لأن 2i > e ، فإن خاصية الكومة صحيحة للنطاق الموسع حديثًا ، ولا داعي لأي إجراء). بتبديل القيمتين a [ i ] و a [ j ]، يتم إثبات خاصية الكومة للموضع i . عند هذه النقطة، تكمن المشكلة الوحيدة في أن خاصية الكومة قد لا تكون صحيحة للفهرس j . يتم تطبيق دالة "التصفية التنازلية" بشكل متكرر ذيليًا على الفهرس j حتى يتم إثبات خاصية الكومة لجميع العناصر.

تتميز دالة التصفية التنازلية بالسرعة. فهي لا تحتاج في كل خطوة إلا إلى مقارنتين وعملية تبديل واحدة. وتتضاعف قيمة الفهرس الذي تعمل عليه في كل تكرار، بحيث لا يتطلب الأمر أكثر من log 2 e خطوة.

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

تستغرق عملية دمج كومتين ثنائيتين Θ( n ) للكومتين متساويتي الحجم. وأفضل ما يمكن فعله (في حالة التنفيذ باستخدام المصفوفات) هو ببساطة دمج مصفوفتي الكومة وبناء كومة من الناتج. [ 13 ] يمكن دمج كومة مكونة من n عنصرًا مع كومة مكونة من k عنصرًا باستخدام O(log n log k ) من مقارنات المفاتيح، أو، في حالة التنفيذ باستخدام المؤشرات، في زمن O(log n log k ). [ 14 ] عُرضت خوارزمية لتقسيم كومة مكونة من n عنصرًا إلى كومتين مكونتين من k و nk عنصرًا على التوالي، استنادًا إلى رؤية جديدة للكومات كمجموعات مرتبة من الكومات الفرعية. [ 15 ] تتطلب الخوارزمية O(log n * log n ) من المقارنات. كما تُقدم هذه الرؤية خوارزمية جديدة وبسيطة من حيث المفهوم لدمج الكومات. عندما يكون الدمج مهمة شائعة، يوصى بتنفيذ كومة مختلفة، مثل أكوام ذات الحدين ، والتي يمكن دمجها في O(log n ).

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

من الممكن تعديل بنية الكومة لجعل استخراج كل من أصغر عنصر وأكبر عنصر ممكنًا فييا{\displaystyle O}(سجل⁡ن){\displaystyle (\log n)}[ 16 ] لتحقيق ذلك ، تتناوب الصفوف بين كومة الحد الأدنى وكومة الحد الأقصى. الخوارزميات متشابهة تقريبًا، ولكن في كل خطوة، يجب مراعاة الصفوف المتناوبة مع المقارنات المتناوبة. الأداء مماثل تقريبًا لأداء كومة أحادية الاتجاه عادية. يمكن تعميم هذه الفكرة لتشمل كومة الحد الأدنى-الحد الأقصى-الوسيط.

اشتقاق معادلات المؤشر

في الكومة القائمة على المصفوفات، يمكن تحديد مواقع أبناء ووالد عقدة ما من خلال عمليات حسابية بسيطة على فهرس تلك العقدة. يستنتج هذا القسم المعادلات ذات الصلة للكومات التي يكون جذرها عند الفهرس 0، مع ملاحظات إضافية حول الكومات التي يكون جذرها عند الفهرس 1.

ولتجنب الالتباس، نحدد مستوى العقدة على أنه المسافة بينها وبين الجذر، بحيث يشغل الجذر نفسه المستوى 0.

العقد الفرعية

بالنسبة لعقدة عامة تقع عند الفهرس i (بدءًا من 0)، سنقوم أولاً باستنتاج فهرس ابنها الأيمن،يمين=2أنا+2{\displaystyle {\text{right}}=2i+2}.

لنفترض أن العقدة i تقع في المستوى L ، ولاحظ أن أي مستوى l يحتوي بالضبط على2ل{\displaystyle 2^{l}}العقد. علاوة على ذلك، يوجد بالضبط2ل+1-1{\displaystyle 2^{l+1}-1}العقد الموجودة في الطبقات حتى الطبقة l (فكر في الحساب الثنائي؛ 0111...111 = 1000...000 - 1). نظرًا لأن الجذر مخزن عند 0، فسيتم تخزين العقدة k عند الفهرس(ك-1){\displaystyle (k-1)}. بجمع هذه الملاحظات معًا ينتج التعبير التالي لمؤشر العقدة الأخيرة في الطبقة l .

آخر(ل)=(2ل+1-1)-1=2ل+1-2{\displaystyle {\text{last}}(l)=(2^{l+1}-1)-1=2^{l+1}-2}

لنفترض وجود j عقدة بعد العقدة i في الطبقة L، بحيث

أنا=آخر(ل)-ج=(2ل+1-2)-ج{\displaystyle {\begin{alignedat}{2}i=&\quad {\text{last}}(L)-j\\=&\quad (2^{L+1}-2)-j\\\end{alignedat}}}

يجب أن يكون لكل عقدة من هذه العقد j طفلان بالضبط، لذلك يجب أن يكون هناك2ج{\displaystyle 2j}العقد التي تفصل الابن الأيمن للعقدة i عن نهاية طبقتها (ل+1{\displaystyle L+1}).

يمين=last(L + 1)-2ج=(2ل+2-2)-2ج=2(2ل+1-2-ج)+2=2أنا+2{\displaystyle {\begin{alignedat}{2}{\text{right}}=&\quad {\text{last(L + 1)}}-2j\\=&\quad (2^{L+2}-2)-2j\\=&\quad 2(2^{L+1}-2-j)+2\\=&\quad 2i+2\end{alignedat}}}

بملاحظة أن الابن الأيسر لأي عقدة يسبق دائمًا الابن الأيمن بموضع واحد، نحصل علىغادر=2أنا+1{\displaystyle {\text{left}}=2i+1}.

إذا كان الجذر موجودًا في الفهرس 1 بدلاً من 0، فإن العقدة الأخيرة في كل مستوى ستكون في الفهرس 1.2ل+1-1{\displaystyle 2^{l+1}-1}يؤدي استخدام هذا في جميع أنحاء العملية إلىغادر=2أنا{\displaystyle {\text{left}}=2i}ويمين=2أنا+1{\displaystyle {\text{right}}=2i+1}بالنسبة للأكوام التي يكون جذرها عند 1.

العقدة الأبوية

كل عقدة غير جذرية هي إما الابن الأيسر أو الأيمن لعقدتها الأبوية، لذا يجب أن يتحقق أحد الشرطين التاليين:

  • أنا=2×(أحد الوالدين)+1{\displaystyle i=2\times ({\text{parent}})+1}
  • أنا=2×(أحد الوالدين)+2{\displaystyle i=2\times ({\text{parent}})+2}

لذلك،

أحد الوالدين=أنا-12أوأنا-22{\displaystyle {\text{parent}}={\frac {i-1}{2}}\;{\textrm {or}}\;{\frac {i-2}{2}}}

والآن لننظر في التعبير⌊أنا-12⌋{\displaystyle \left\lfloor {\dfrac {i-1}{2}}\right\rfloor }.

إذا كانت العقدةأنا{\displaystyle i}إذا كان هذا ابنًا أيسرًا، فسيعطي النتيجة فورًا، ومع ذلك، فإنه يعطي أيضًا النتيجة الصحيحة إذا كانت العقدةأنا{\displaystyle i}هو الابن العاق. في هذه الحالة،(أنا-2){\displaystyle (i-2)}يجب أن يكون زوجيًا، وبالتالي(أنا-1){\displaystyle (i-1)}لا بد أن يكون الأمر غريباً.

⌊أنا-12⌋=⌊أنا-22+12⌋=أنا-22=أحد الوالدين{\displaystyle {\begin{alignedat}{2}\left\lfloor {\dfrac {i-1}{2}}\right\rfloor =&\quad \left\lfloor {\dfrac {i-2}{2}}+{\dfrac {1}{2}}\right\rfloor \\=&\quad {\frac {i-2}{2}}\\=&\quad {\text{parent}}\end{alignedat}}}

لذلك، وبغض النظر عما إذا كانت العقدة ابنًا أيسرًا أو أيمنًا، يمكن إيجاد والدها من خلال التعبير التالي:

أحد الوالدين=⌊أنا-12⌋{\displaystyle {\text{parent}}=\left\lfloor {\dfrac {i-1}{2}}\right\rfloor }

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

الكومة الثنائية هي حالة خاصة من الكومة ذات الـ d حيث d = 2.

ملخص أوقات التشغيل

فيما يلي تعقيدات زمنية [ 17 ] لهياكل بيانات الكومة المختلفة. يشير الاختصار am. إلى أن التعقيد المذكور هو التعقيد المُستهلك، وإلا فهو تعقيد أسوأ حالة. لمعرفة معنى " O ( f )" و" Θ ( f )"، راجع ترميز Big O. تفترض أسماء العمليات وجود كومة دنيا.

عمليةالبحث عن الحد الأدنىحذف الحد الأدنىمفتاح التناقصأدخلاندماجmake-heap [ c ]
ثنائي [ 17 ]Θ (1)Θ (log n ) Θ (log n ) Θ (log n ) Θ ( n )Θ ( n )
الانحراف [ 18 ]Θ (1)O (log n ) am. O (log n ) am. O (log n ) am. O (log n ) am. Θ ( n ) am.
يساري [ 19 ]Θ (1)Θ (log n ) Θ (log n ) Θ (log n ) Θ (log n ) Θ ( n )
ذات الحدين [ 17 ] [ 21 ]Θ (1)Θ (log n ) Θ (log n ) Θ (1) صباحًا.Θ (log n ) [ d ] Θ ( n )
التوزيع الثنائي المائل [ 22 ]Θ (1)Θ (log n ) Θ (log n ) Θ (1)Θ (log n ) [ d ] Θ ( n )
2-3 كومة [ 24 ]Θ (1)O (log n ) am. Θ (1)Θ (1) صباحًا.O (log n ) [ d ] Θ ( n )
الانحراف من الأسفل إلى الأعلى [ 18 ]Θ (1)O (log n ) am. O (log n ) am. Θ (1) صباحًا.Θ (1) صباحًا.Θ ( n ) am.
الاقتران [ 25 ]Θ (1)O (log n ) am. o (log n ) am. [ e ] Θ (1)Θ (1)Θ ( n )
الاقتران بالرتب [ 28 ]Θ (1)O (log n ) am. Θ (1) صباحًا.Θ (1)Θ (1)Θ ( n )
فيبوناتشي [ 17 ] [ 29 ]Θ (1)O (log n ) am. Θ (1) صباحًا.Θ (1)Θ (1)Θ ( n )
فيبوناتشي الصارم [ 30 ] [ f ]Θ (1)Θ (log n ) Θ (1)Θ (1)Θ (1)Θ ( n )
برودال [ 31 ] [ f ]Θ (1)Θ (log n ) Θ (1)Θ (1)Θ (1)Θ ( n ) [ 32 ]
  1. ↑ في الواقع، يمكن إثبات أن هذه العملية تستغرقزمنًا قدره Θ( n log n ) في أسوأ الحالات ، مما يعني أن n log n هو أيضًا حد أدنى تقاربي للتعقيد. [ 1 ] : 167 أما في الحالة المتوسطة (بحساب المتوسط ​​على جميع تباديل n منالمدخلات)، فإن الطريقة تستغرق زمنًا خطيًا. [ 8 ]
  2. ↑ هذا لا يعني أنه يمكن إجراء الفرز في وقت خطي لأن بناء الكومة هو الخطوة الأولى فقط من خوارزمية فرز الكومة .
  3. ↑ عملية بناء الكومة هي عملية إنشاء كومة من سلسلة من n عنصرًا غير مُرتبة. يمكن إنجازها فيزمن Θ ( n ) بينما تعمل خوارزمية دمج العناصر في زمن O (log n ) (حيث يمكن توزيع كلا التعقيدين). [ 18 ] [ 19 ] وتحقق خوارزمية أخرى زمن Θ ( n ) للكومات الثنائية. [ 20 ] 
  4. بالنسبة للأكوام المستمرة (التي لا تدعم تقليل المفتاح )، يُقلل تحويل عام تكلفة دمج العناصر إلى تكلفة إدراجها ، بينما تكون التكلفة الجديدة لحذف الحد الأدنى هي مجموع التكاليف القديمة لكل من حذف الحد الأدنى ودمج العناصر. [23] هنا ، يجعل هذا التحويل دمج العناصر يعمل في زمن Θ (1) (مُستهلك، إذا كانت تكلفة الإدراج كذلك)، بينما لا يزال حذف الحد الأدنى يعمل في زمن O ( log n ). عند تطبيقه على أكوام ذات توزيع ثنائي مائل، ينتج عنه طوابير برودال-أوكاساكي، وهي أكوام مستمرة ذات تعقيدات مثلى في أسوأ الحالات. [ 22 ] 
  5. ↑ الحد الأدنى لـΩ(سجل⁡سجل⁡ن)،{\displaystyle \Omega (\log \log n),}[ 26 ] الحد الأعلى لـيا(22سجل⁡سجل⁡ن).{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}[ 27 ]
  6. تُحقق طوابير برودال وأكوام فيبوناتشي الصارمة أفضل تعقيد في أسوأ الحالات للأكوام. وقد وُصفت في البداية بأنها هياكل بيانات إجرائية. أما طابور برودال-أوكاساكي فهو هيكل بيانات مستمر يحقق نفس المستوى الأمثل، باستثناء أنهلا يدعم خاصية تقليل المفتاح .

مراجع

  1. 1 2 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات (  الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN 0-262-03384-4.
  2. ↑ ويليامز، جيه دبليو جيه (1964)، "الخوارزمية 232 - فرز الكومة"، اتصالات رابطة آلات الحوسبة ، 7 (6): 347-348 ، doi : 10.1145/512274.3734138
  3. ↑ واي ناراهاري، "الأكوام الثنائية" ، هياكل البيانات والخوارزميات
  4. ↑ بورتر، توماس؛ سيمون، إستفان (سبتمبر 1975). "الإدراج العشوائي في بنية قائمة انتظار ذات أولوية". معاملات IEEE في هندسة البرمجيات . SE-1 (3): 292-298 . Bibcode : 1975ITSEn...1..292P . doi : 10.1109/TSE.1975.6312854 . ISSN 1939-3520 . S2CID 18907513 .  
  5. ↑ ميلهورن، كورت؛ تساكاليديس، أ. (فبراير 1989). "هياكل البيانات" . جامعة سارلاند : 27. doi : 10.22028/D291-26123 . قام بورتر وسيمون [171] بتحليل متوسط ​​تكلفة إدخال عنصر عشوائي في كومة عشوائية من حيث عمليات التبادل. وأثبتا أن هذا المتوسط ​​محدود بالثابت 1.61. لا يمكن تعميم برهانهما على متواليات الإدخالات لأن الإدخالات العشوائية في أكوام عشوائية لا تُنشئ أكوامًا عشوائية. تم حل مشكلة الإدخال المتكرر بواسطة بولوباس وسيمون [27]؛ حيث أظهرا أن العدد المتوقع لعمليات التبادل محدود بـ 1.7645. تمت دراسة أسوأ تكلفة للإدخالات والحذف بواسطة جونيت ومونرو [84]. إنهم يعطون حدودًا لعدد المقارنات على التوالي، وهي log log n + O(1) و log n + log n* + O(1).
  6. ↑ "python/cpython/heapq.py" . GitHub . تم الاسترجاع في 2020-08-07 .
  7. ↑ "heapq — خوارزمية قائمة الانتظار في الكومة — توثيق بايثون 3.8.5" . docs.python.org . تاريخ الاسترجاع: 7 أغسطس 2020. heapq.heappushpop(heap, item): إضافة عنصر إلى الكومة، ثم إزالة أصغر عنصر منها وإرجاعه. يُنفذ هذا الإجراء المدمج بكفاءة أعلى من استخدام heappush() متبوعًا باستدعاء منفصل لـ heappop().
  8. 1 2 هايوارد، رايان؛ ماكديارميد، كولين (1991). "تحليل الحالة المتوسطة لبناء الكومة عن طريق الإدخال المتكرر" (ملف PDF) . مجلة الخوارزميات . 12 : 126-153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . مؤرشف من الأصل (ملف PDF) بتاريخ 2016-02-05 . تم الاسترجاع بتاريخ 2016-01-28 . 
  9. ↑ سوشينيك، ماريك أ. (2012)، "تحليل أولي ولكنه دقيق لأسوأ الحالات لبرنامج بناء الكومة لفلويد" ، Fundamenta Informaticae ، 120 (1): 75-92 ، doi : 10.3233/FI-2012-751.
  10. ↑ دوبركات، إرنست إي. (مايو 1984). "تحليل الحالة المتوسطة لخوارزمية فلويد لبناء الأكوام" (ملف PDF) . المعلومات والتحكم . 6 (2): 114-131 . doi : 10.1016/S0019-9958(84)80053-4 .
  11. ↑ باسانين، تومي (نوفمبر 1996). تحليل الحالة المتوسطة الأولية لخوارزمية فلويد لبناء الأكوام (تقرير فني). مركز توركو لعلوم الحاسوب. CiteSeerX 10.1.1.15.9526 . ISBN  951-650-888-X. التقرير الفني رقم 64 الصادر عن TUCS. تجدر الإشارة إلى أن هذه الورقة تستخدم مصطلح فلويد الأصلي "siftup" لما يسمى الآن "sifting down " .
  12. ↑ كامب، بول-هينينغ (11 يونيو 2010). "أنت تفعل ذلك بشكل خاطئ" . مجلة ACM Queue . المجلد 8، العدد 6.  
  13. ↑ كريس ل. كوزماول. "كومة ثنائية". مؤرشف بتاريخ 8 أغسطس 2008 في أرشيف الإنترنت . قاموس الخوارزميات وهياكل البيانات، بول إي. بلاك، محرر، المعهد الوطني الأمريكي للمعايير والتكنولوجيا. 16 نوفمبر 2009.
  14. ↑ J.-R. Sack and T. Strothotte "An Algorithm for Merging Heaps" , Acta Informatica 22, 171-186 (1985).
  15. ↑ ساك، يورغ-روديغر ؛ ستروثوت، توماس (1990). "توصيف الأكوام وتطبيقاتها" . المعلومات والحوسبة . 86 : 69-86 . doi : 10.1016/0890-5401(90)90026-E .
  16. ↑ أتكينسون، دكتور في الطب ؛ جيه-آر. ساك ؛ إن. سانتورو وتي. ستروثوت (1 أكتوبر 1986). "أكوام الحد الأدنى والحد الأقصى وقوائم الانتظار ذات الأولوية المعممة" (ملف PDF) . تقنيات البرمجة وهياكل البيانات. مجلة الاتصالات ACM، 29(10): 996-1000. مؤرشف من الأصل (ملف PDF) في 27 يناير 2007. تم الاطلاع عليه في 29 أبريل 2008 .
  17. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  18. 1 2 3 سليتور، دانيال دومينيك ؛ تارجان، روبرت إندري (فبراير 1986). "الأكوام ذاتية التعديل" . مجلة SIAM للحوسبة . 15 (1): 52-69 . CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  19. 1 2 تارجان، روبرت (1983). "3.3. أكوام اليسار". هياكل البيانات وخوارزميات الشبكات . ص 38-42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  20. ↑ هايوارد، رايان؛ ماكديارميد، كولين (1991). "تحليل الحالة المتوسطة لبناء الكومة عن طريق الإدخال المتكرر" (ملف PDF) . مجلة الخوارزميات . 12 : 126-153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . مؤرشف من الأصل (ملف PDF) بتاريخ 2016-02-05 . تم الاطلاع عليه بتاريخ 2016-01-28 . 
  21. ↑ "الكومة ذات الحدين | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 30-09-2019 .
  22. 1 2 برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  23. ↑ أوكاساكي، كريس (1998). "10.2. التجريد الهيكلي". هياكل البيانات الوظيفية البحتة ( الطبعة الأولى). الصفحات 158-162 . ISBN   9780521631242.
  24. ↑ تاكاوكا، تاداو (1999)، نظرية الأكوام 2-3 (ملف PDF) ، ص 12 
  25. ↑ إياكونو، جون (2000)، "تحسين الحدود العليا لأكوام الاقتران"، وقائع ورشة العمل الإسكندنافية السابعة حول نظرية الخوارزميات (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1851، دار نشر سبرينغر، الصفحات 63-77 ، arXiv : 1110.4428 ، CiteSeerX 10.1.1.748.7812 ، doi : 10.1007/3-540-44985-X_5 ، ISBN    3-540-67690-2
  26. ↑ فريدمان، مايكل لورانس (يوليو 1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 46 (4): 473-501 . doi : 10.1145/320211.320214 .
  27. ↑ بيتي، سيث (2005). نحو تحليل نهائي لأكوام الاقتران (ملف PDF) . وقائع ندوة FOCS '05 السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب. الصفحات 174-183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  28. ^ هيوبلر، بيرنهارد. سين، سيدهارتا؛ تارجان ، روبرت إي. (نوفمبر 2011). "أكوام الاقتران بالرتبة" (PDF) . سيام ج. الحوسبة . 40 (6): 1463–1485 . دوى : 10.1137/100785351 .
  29. ↑ فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (يوليو 1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  30. ↑ برودال، جيرث ستولتينغ ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (2012). أكوام فيبوناتشي الصارمة (ملف PDF) . وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة - STOC '12. الصفحات 1177-1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  31. ↑ برودال، جيرث س. ( 1996)، "طوابير الأولوية الفعالة في أسوأ الحالات" (ملف PDF) ، وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 52-58 
  32. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2004). "7.3.6. بناء الكومة من الأسفل إلى الأعلى". هياكل البيانات والخوارزميات في جافا ( الطبعة الثالثة). ص 338-341 . ISBN   0-471-46983-1.