Time and Space Complexity

تعقيد الوقت:

• أفضل، ومتوسط، وأسوأ حالة: O(n log n)
  • بناء الكومة (heap) يستغرق O(n)، وكل عملية استخراج من الـ n عمليات تكلف O(log n) لعملية الغربلة للأسفل (sift-down). لا توجد حالة مدخلات سيئة تؤدي إلى تدهور الأداء.

تعقيد المساحة:

• O(1)
  • يقوم فرز الكومة (Heap Sort) بإعادة ترتيب العناصر داخل المصفوفة الأصلية ويحتاج فقط إلى كمية ثابتة من الذاكرة الإضافية.

ملخص:

• يجمع فرز الكومة (Heap Sort) بين وقت تشغيل مضمون قدره O(n log n) مع مساحة إضافية قدرها O(1)، وهو مزيج لا يوفره كل من فرز الدمج (Merge Sort) والفرز السريع (Quick Sort) معاً.
• إنه غير مستقر (قد يتغير الترتيب النسبي للعناصر المتساوية)، وهو المقايضة الرئيسية فيه.