الترتيب بالكومة

الترتيب بالكومة هو ترتيب بالاختيار بطريقة أفضل لإيجاد أكبر قيمة. يحتفظ بالقيم غير المرتبة في كومة، وهي شجرة مخزنة داخل القائمة نفسها، تكون فيها أكبر قيمة دائمًا في القمة. واستخراجها وإصلاح الكومة يستغرقان نحو log n خطوة بدلًا من مسح كامل.

كومة مرسومة كشجرة ثنائية فوق القيم نفسها على شكل أعمدة، وأكبر قيمة في الجذر تنتقل بالتبديل إلى نهاية القائمة
كومة مرسومة كشجرة ثنائية فوق القيم نفسها على شكل أعمدة، وأكبر قيمة في الجذر تنتقل بالتبديل إلى نهاية القائمة

شجرة داخل قائمة

الكومة الثنائية شجرة لا تحتاج إلى مؤشرات. الموضع 0 هو الجذر، وابنا الموضع i هما الموضعان 2i + 1 و2i + 2، فالموضعان 1 و2 ابنا الجذر، والمواضع من 3 إلى 6 المستوى التالي، وهكذا. كل مستوى ممتلئ إلا الأخير، الذي يُملأ من أوله. في الكومة العظمى يكون كل أب أكبر من أبنائه أو مساويًا لهم، لذا تكون أكبر قيمة دائمًا في الجذر.

الإنزال

عملية واحدة تؤدي كل العمل. لإنزال قيمة، قارنها بأبنائها. إذا كان الابن الأكبر أكبر من القيمة، يتبادلان، وتُقارن القيمة بأبنائها الجدد. تتوقف حين لا يكون أي ابن أكبر منها، أو حين تبلغ القاع. ولأن للشجرة نحو log₂ n مستوى فقط، يستغرق الإنزال نحو 2 log₂ n مقارنة على الأكثر.

بناء الكومة ثم الترتيب

لبناء الكومة، أنزِل كل أب، من آخر أب رجوعًا إلى الجذر. كل شجرة فرعية تكون كومة قبل أن ينزل أبوها فيها. ثم رتّب: بدّل الجذر، أي أكبر قيمة، مع آخر قيمة في الكومة. تصبح تلك القيمة في مكانها النهائي. تقصر الكومة بمقدار واحد، وتنزل القيمة التي وصلت إلى الجذر لإصلاحها. كرّر حتى تبقى قيمة واحدة.

مثال

خذ 5, 1, 4, 2, 8. عند بناء الكومة ينزل 1 تحت 8، ثم ينزل 5 تحت 8، فتصبح القائمة 8, 5, 4, 2, 1. الآن يُبدَّل 8 إلى النهاية؛ ويصل 1 إلى الجذر وينزل متجاوزًا 5 و2: 5, 2, 4, 1 | 8. ثم يذهب 5 إلى النهاية وينزل 1 متجاوزًا 4: 4, 2, 1 | 5, 8. وتُكمل جولتان أخريان القائمة: 1, 2, 4, 5, 8، بعد 12 مقارنة و10 تبديلات.

نقاط القوة والضعف

يستغرق الترتيب بالكومة وقتًا متناسبًا مع n log n حتى في أسوأ حالة، ولا يحتاج إلى ذاكرة إضافية. قد يتباطأ الترتيب السريع إلى n²، ويحتاج الترتيب بالدمج إلى مخزن مؤقت بطول القائمة، لذا فالترتيب بالكومة هو البديل الآمن: فخوارزمية introsort، التي تستخدمها مكتبة C++ القياسية، تنتقل إليه حين تسوء تقسيمات الترتيب السريع. وعلى الحواسيب الحقيقية يكون عادةً أبطأ من كليهما، لأنه يقفز بين مواضع متباعدة في القائمة، وهو غير مستقر. نشر J. W. J. Williams الترتيب بالكومة، مع الكومة الثنائية، عام 1964.

استكشفه

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

الأسئلة المتداولة

ما التعقيد الزمني للترتيب بالكومة؟

O(n log n) في أفضل الحالات ومتوسطها وأسوئها. يستغرق بناء الكومة O(n)، وتستغرق كل عملية من عمليات الاستخراج الـ n − 1 زمن O(log n). ويرتب في الموضع نفسه بذاكرة إضافية O(1).

ما الفرق بين الترتيب بالكومة والترتيب بالاختيار؟

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

فيمَ تُستخدم الكومة غير الترتيب؟

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

هل الترتيب بالكومة مستقر؟

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

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب الترتيب بالكومة