What is a Heap?

الـ heap هي بنية بيانات على شكل شجرة تلتزم بقاعدة ثابتة بسيطة: كل عقدة أب أصغر من (أو تساوي) أبنائها. أصغر قيمة توجد دائماً عند الجذر، وتكون جاهزة للقراءة في زمن قدره O(1). يُطلق على هذا النوع تحديداً اسم min-heap؛ أما الصورة المعاكسة التي تضع القيمة الأكبر عند الجذر فتسمى max-heap.

الجزء الذكي يكمن في التخزين. على الرغم من أننا نتصورها كشجرة، إلا أن الـ heap تعيش داخل مصفوفة (array) مسطحة. بالنسبة للعقدة عند الفهرس i:

• العقدة الأب موجودة عند الفهرس (i - 1) / 2.
• الابن الأيسر موجود عند الفهرس 2 * i + 1.
• الابن الأيمن موجود عند الفهرس 2 * i + 2.

لا توجد مؤشرات (pointers)، ولا كائنات عقد (node objects): مجرد عمليات حسابية على الفهارس. وهذا يجعل الـ heaps صديقة جداً للذاكرة المخبئية (cache-friendly) وسهلة التنفيذ.

العمليات الخمس الرئيسية على الـ min-heap هي:

1. Peek: إرجاع أصغر قيمة (الجذر).
2. Insert: إضافة قيمة ورفعها (bubble up) إلى مكانها الصحيح.
3. ExtractMin: إزالة وإرجاع أصغر قيمة.
4. Size: إرجاع عدد القيم المخزنة.
5. IsEmpty: التحقق مما إذا كانت الـ heap فارغة.

لنقم بإنشاء فئة MinHeap!