ما معنى heap في الخوارزميات وهياكل البيانات؟ شرح مبسّط وعملي

الـ heap (ويُترجم أحيانًا إلى "الكومة") هو بنية بيانات على شكل شجرة تحتفظ دائمًا بأكبر عنصر أو أصغر عنصر عند الجذر، بحيث يمكنك الوصول إليه في زمن ثابت والحصول عليه أو حذفه بسرعة. تخيّله كطابور ذكي: العناصر لا تُرتَّب بالكامل، لكن الأهم منها يبقى في المقدمة دائمًا. هذه الخاصية البسيطة هي ما يجعله العمود الفقري لما يُعرف بـ "طابور الأولوية" (Priority Queue)، ولخوارزميات مثل دايكسترا وترتيب الكومة (Heap Sort).

أولًا: انتبه إلى الالتباس الأكثر شيوعًا

قبل الدخول في التفاصيل، هناك خلط يقع فيه كثير من المبتدئين، ومن المهم توضيحه لأنه يُربك البحث نفسه. كلمة heap تُستخدم بمعنيين مختلفين تمامًا:

• الـ heap كبنية بيانات: وهو موضوع هذا المقال، أي الشجرة التي تُنظّم العناصر حسب الأولوية.
• الـ heap كمنطقة ذاكرة: وهي المساحة التي يخصّصها البرنامج ديناميكيًا أثناء التشغيل (مقابل الـ Stack). هذه لا علاقة لها ببنية البيانات إطلاقًا، رغم تطابق الاسم.

إذا كنت تدرس الخوارزميات، فالمقصود هو المعنى الأول. أما إن كنت تصحّح خطأ "out of memory" في برنامجك، فأنت أمام المعنى الثاني.

كيف يعمل الـ heap فعليًا؟

الـ heap هو شجرة ثنائية "كاملة" (Complete Binary Tree)، أي أنها ممتلئة من الأعلى للأسفل ومن اليسار لليمين دون فجوات. وتخضع لقاعدة واحدة تُسمى "خاصية الكومة": كل عقدة أكبر (أو أصغر) من أبنائها.

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

• ابنه الأيسر في الموضع 2i + 1
• ابنه الأيمن في الموضع 2i + 2
• أبوه في الموضع (i - 1) / 2

بهذه المعادلات البسيطة نتنقّل في "الشجرة" دون أي مؤشرات، ونوفّر ذاكرة كبيرة.

Max-Heap أم Min-Heap؟

النوعان متطابقان في الفكرة ويختلفان فقط في اتجاه الترتيب. اختر بينهما حسب ما تريد الوصول إليه بسرعة:

المعيار	Max-Heap	Min-Heap
العنصر في الجذر	الأكبر	الأصغر
القاعدة	كل عقدة ≥ أبنائها	كل عقدة ≤ أبنائها
الاستخدام النموذجي	إيجاد أكبر قيمة، Heap Sort تنازلي	طابور الأولوية، دايكسترا، أصغر قيمة
مثال جاهز	—	فئة PriorityQueue في جافا

القاعدة الذهنية: إن كنت تسأل باستمرار "ما هو الأكبر؟" استخدم Max-Heap، وإن كنت تسأل "ما هو الأصغر/الأعلى أولوية؟" استخدم Min-Heap.

العمليات الأساسية خطوة بخطوة

1. إضافة عنصر (Insert)

1. ضع العنصر الجديد في نهاية المصفوفة (آخر ورقة في الشجرة).
2. قارنه بأبيه، فإن خالف خاصية الكومة، بادِل بينهما.
3. كرّر الصعود لأعلى حتى يستقر في مكانه الصحيح. تُسمى هذه العملية "الغربلة لأعلى" (Sift Up)، وكلفتها O(log n).

2. حذف الجذر (Extract Min/Max)

1. خذ عنصر الجذر (وهو أكبر أو أصغر عنصر).
2. انقل آخر عنصر في المصفوفة إلى مكان الجذر.
3. أنزِله بالمبادلة مع الأصغر (أو الأكبر) من أبنائه حتى تعود الخاصية. تُسمى "الغربلة لأسفل" (Sift Down)، وكلفتها O(log n).

3. بناء heap من مصفوفة جاهزة (Build Heap)

بدلًا من إدراج العناصر واحدًا تلو الآخر بكلفة O(n log n)، توجد خوارزمية أذكى تبني الـ heap دفعة واحدة في زمن O(n) فقط، عبر تطبيق الغربلة لأسفل بدءًا من آخر عقدة غير ورقية صعودًا إلى الجذر. هذه نقطة مهمة كثيرًا ما تُسأل في المقابلات.

أين يُستخدم الـ heap عمليًا؟

• طوابير الأولوية: جدولة المهام في أنظمة التشغيل، حيث تُنفَّذ المهمة الأعلى أولوية أولًا.
• خوارزمية دايكسترا وA*: لاختيار العقدة ذات المسافة الأقل بسرعة أثناء إيجاد أقصر مسار.
• Heap Sort: خوارزمية ترتيب بكلفة O(n log n) وذاكرة إضافية شبه معدومة.
• مسألة "أكبر/أصغر K عنصر": الوصول إلى أعلى النتائج في تدفق بيانات ضخم دون ترتيبه كاملًا.

نصيحة عملية وخطأ شائع

في معظم لغات البرمجة لا تحتاج إلى كتابة الـ heap يدويًا؛ استخدم المكتبة الجاهزة: PriorityQueue في جافا (وهي Min-Heap افتراضيًا)، وheapq في بايثون (Min-Heap أيضًا)، وpriority_queue في C++ (وهي Max-Heap افتراضيًا). لاحظ اختلاف الاتجاه الافتراضي بين اللغات، فهذا مصدر أخطاء متكرر.

الخطأ الأكثر شيوعًا: توقّع أن الـ heap "مرتَّب بالكامل". هو ليس كذلك. الـ heap يضمن فقط ترتيب الجذر بالنسبة لأبنائه، فلو مررت على المصفوفة من أولها لآخرها فلن تجدها مرتبة. إن أردت ترتيبًا كاملًا فاسحب العناصر واحدًا تلو الآخر، أو استخدم شجرة بحث ثنائية بدلًا منه.

الأسئلة الشائعة

ما الفرق بين الـ heap وشجرة البحث الثنائية (BST)؟ الـ heap يمنحك الأكبر أو الأصغر فورًا لكنه لا يدعم البحث المرتّب أو إيجاد قيمة وسطية بكفاءة. أما BST فيحافظ على ترتيب كامل ويدعم البحث بكلفة O(log n)، لكنه أبطأ في استخراج القيمة القصوى المتكررة.

هل الـ heap أسرع من الترتيب الكامل؟ نعم إن كنت تحتاج فقط إلى العنصر الأهم مرارًا. استخراج الأكبر يكلّف O(log n)، بينما ترتيب المصفوفة كاملة يكلّف O(n log n) لمرة واحدة.

هل الـ heap دائمًا شجرة ثنائية؟ غالبًا نعم، لكن توجد أنواع أخرى مثل Binary Heap وBinomial Heap وFibonacci Heap، ولكلٍّ منها كلف مختلفة تُستخدم في حالات متقدمة.

كيف أختار بين Max-Heap وMin-Heap؟ اسأل نفسك: أي طرف أحتاج الوصول إليه بسرعة؟ إن كان الأكبر فاستخدم Max-Heap، وإن كان الأصغر أو الأعلى أولوية فاستخدم Min-Heap.