ما هو الكومة (Heap) وكيف تطبق طابور الأولويات (Priority Queue)؟

Question

Accepted Answer

**كومة ثنائية** (binary heap) هي شجرة ثنائية كاملة مخزنة في مصفوفة تحافظ على **خاصية الكومة** (heap property): في **كومة صغرى** (min-heap)، كل عنصر أب يكون ≤ أطفاله، لذا **القيمة الصغرى موجودة دائماً عند الجذر**. هذا يجعلها **التطبيق المعياري لطابور الأولويات**.

## تخطيط المصفوفة

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## العمليات

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## التعقيد الزمني

| العملية | الوقت |
|---|---|
| أخذ القيمة الصغرى/الكبرى | O(1) |
| إدراج (push) | O(log n) |
| استخراج (pop) | O(log n) |
| بناء كومة من n عنصر | O(n) |

## متى تستخدم

- **الجدولة** حسب الأولوية (مثل جدولة مهام النظام).
- **خوارزميات Dijkstra وPrim** لأقصر مسار وشجرة الامتداد الصغرى.
- **مسائل Top-K** والوسيط في البيانات المتدفقة.
- **فرز الكومة** (Heap sort) بتعقيد O(n log n) موضعي.

## لماذا مهم

الكومة تمنحك العنصر الأكثر أهمية بلحظة دون الحاجة لبقاء كل شيء مرتباً بالكامل، وهو أرخص بكثير من إعادة الفرز.

هي الأساس لخوارزميات الأولويات وأداة متكررة في المقابلات للأسئلة "k أكبر/أصغر".

العملية	الوقت
أخذ القيمة الصغرى/الكبرى	O(1)
إدراج (push)	O(log n)
استخراج (pop)	O(log n)
بناء كومة من n عنصر	O(n)