35. خوارزمية فرز الكومة (Heap Sort)

Heap Sort هي خوارزمية فرز فعالة تعتمد على المقارنة وتستفيد من هيكل بيانات Max Heap.

خطوات Heap Sort

تتكون Heap Sort من مرحلتين رئيسيتين:

1. بناء Max Heap: تحويل مصفوفة المدخلات إلى هيكل Max Heap. تستغرق هذه العملية وقتاً قدره O(N).
2. مرحلة الفرز: استخراج العنصر الأقصى (الجذر) بشكل متكرر ووضعه في نهاية المصفوفة. بعد الاستخراج، يتم إعادة بناء خاصية الكومة للعناصر المتبقية.
   • تبديل الجذر (أكبر عنصر) بالعنصر الأخير في الكومة.
   • تقليل حجم الكومة بمقدار واحد.
   • إصلاح خاصية الكومة على الكومة الجديدة والأصغر (عملية تسمى heapify)، والتي تستغرق O(log N).

الكفاءة

• التعقيد الزمني: O(N log N) لجميع الحالات (أسوأ، متوسط، أفضل). وهذا لأن البناء يستغرق O(N)، وعمليات الاستخراج/البناء N تستغرق N * O(log N).
• التعقيد المكاني: مساحة مساعدة O(1)، مما يجعلها خوارزمية فرز في الموقع (in-place).