المقارنات
التبديلات
المستخرَجة

  • قيد الإنزال
  • قيد المقارنة
  • تم تبديله
  • في مكانه

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

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

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

كيف يعمل

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

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

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

دائمًا n log n، في الموضع نفسه

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

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

كيف يعمل الترتيب بالكومة؟

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

ما الكومة؟

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

لماذا بناء الكومة سريع؟

معظم القيم قرب أسفل الشجرة ولا يمكنها النزول إلا مستوى أو مستويين. وجمع العمل على كل المستويات يعطي أقل من 2n مقارنة للبناء كله، لا n log n.

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

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

هل تُرسَل أرقامي إلى أي مكان؟

لا. يعمل الترتيب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.

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

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

الانتقال إلى المحرر