الفصل 4: Les tas (Heaps) – Algorithmique et Structures de Données (ASD3)

تتناول هذه المحاضرة الفصل الرابع من مقياس Algorithmique et Structures de Données (ASD3)، والمخصص لدراسة بنية البيانات المعروفة باسم Les tas أو Heaps. تبدأ المحاضرة ببيان مشكلة تنفيذ طابور ذي أولوية باستخدام قائمة عادية أو قائمة مرتبة، مع توضيح التعقيد الزمني لكل حل، ثم تبرز دور الأكوام في تحقيق توازن بين سرعة الإدراج وسرعة استخراج العنصر الأعلى أولوية. بعد ذلك تقدم تعريف الكومة باعتبارها شجرة ثنائية كاملة تحقق خاصية الترتيب، وتوضح الفرق بين Tas-Max حيث تكون قيمة الأب أكبر أو تساوي أبناءه، وTas-Min حيث تكون قيمة الأب أصغر أو تساوي أبناءه. كما تعرض المحاضرة أمثلة توضيحية للبنيتين وتشرح أهميتهما في تنفيذ Priority Queue وفي عدد من خوارزميات الرسوم البيانية. ثم تشرح عمليات الإدراج من خلال إضافة العنصر في أول موضع متاح ثم رفعه تدريجياً حتى تستعاد خاصية الكومة، وكذلك عملية الحذف التي تبدأ بإزالة الجذر وتعويضه بآخر عنصر ثم إنزاله حتى يعود الترتيب الصحيح. تساعد هذه المفاهيم الطالب على فهم كيفية المحافظة على خصائص الكومة وتحليل كفاءة العمليات الأساسية واستعمالها في التطبيقات والخوارزميات.