كيف يعمل فرز الكومة (Heap Sort)؟

Question

Accepted Answer

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

## الفكرة الأساسية

الكومة العظمى تحافظ على العنصر الأكبر في الجذر. بناء الكومة (O(n))، ثم تبديل الجذر إلى النهاية، تقليص الكومة، وإعادة كومة (sift down) — n مرات.

## مثال

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

التنفيذ الكلاسيكي يفعل ذلك في المكان بواسطة sift down داخل المصفوفة.

## التعقيد

- **الوقت:** O(n log n) في جميع الحالات. **المساحة:** O(1) في المكان.

## متى يتم الاستخدام / المزالق

استخدمه عندما تحتاج إلى **O(n log n) مضمون** *و* **O(1) ذاكرة إضافية** (merge sort يحتاج O(n); quicksort يخاطر بـ O(n²)). هو **غير مستقر** وله محلية ذاكرة تخزين مؤقت سيئة، لذلك غالباً ما يكون أبطأ في الممارسة من quicksort. نفس بنية الكومة تشغل **طوابير الأولويات** والعثور على أفضل k عنصر.

## لماذا يهم

فرز الكومة هو الفرز الشائع الوحيد الذي يكون worst-case O(n log n) و في المكان، مما يجعله قيماً في الإعدادات المقيدة بالذاكرة أو المضمونة.

بنية الكومة الأساسية مفيدة على نطاق واسع — طوابير الأولويات، خوارزمية ديجكسترا، و top-k للبث.

هو يرسخ الفكرة بأن بنية البيانات الصحيحة تجعل الخوارزمية فعالة.