الأكوام وقوائم الانتظار ذات الأولوية

قائمة الانتظار ذات الأولوية هي نوع بيانات مجردة تُرجع دائمًا العنصر ذي الأولوية الأعلى (أو الأدنى)؛ والأكوام هي الهياكل الشجرية القياسية التي تنفذها بكفاءة في عمليات الإدراج واستخراج الحد الأدنى.

Definition

قائمة الانتظار ذات الأولوية هي نوع بيانات مجردة تدعم إدراج العناصر ذات الأولويات واستخراج العنصر ذي الأولوية الأعلى؛ والكومة هي بنية بيانات شجرية تحقق خاصية الكومة — حيث يتم ترتيب مفتاح كل عقدة بشكل متسق بالنسبة لأبنائها — وتنفذ قائمة الانتظار ذات الأولوية بكفاءة.

Scope

يغطي هذا الموضوع نوع البيانات المجردة لقائمة الانتظار ذات الأولوية وتطبيقاتها باستخدام الأكوام: الكومة الثنائية وتمثيلها في المصفوفة، خاصية الكومة وعمليات الغربلة للأعلى/للأسفل، الفرز الكومي (heapsort)، والأكوام المتقدمة القابلة للدمج مثل أكوام ذات الحدين (binomial) وأكوام فيبوناتشي (Fibonacci) التي تحسن تكاليف تقليل المفتاح والاتحاد. ويرتبط هذا الموضوع بخوارزميات الرسوم البيانية (دايكسترا، بريم) والمحاكاة المعتمدة على الأحداث، والتي تعتمد على قوائم الانتظار ذات الأولوية.

Core questions

• ما هي العمليات التي تحدد نوع البيانات المجردة لقائمة الانتظار ذات الأولوية، وكيف تنفذها الكومة؟
• كيف تسمح خاصية الكومة بإيجاد الحد الأدنى في وقت ثابت وإدراج/استخراج في وقت لوغاريتمي؟
• كيف يتم تخزين الكومة الثنائية بشكل مضغوط في مصفوفة، وكيف يتم بناؤها في وقت خطي؟
• كيف يستخدم الفرز الكومي (heapsort) الكومة للفرز في مكانه في وقت O(n log n)؟
• متى تحسن الأكوام القابلة للدمج مثل أكوام فيبوناتشي الخوارزميات التي تقلل المفاتيح غالبًا؟

Key concepts

• نوع البيانات المجردة لقائمة الانتظار ذات الأولوية
• خاصية الكومة
• الكومة الثنائية
• تمثيل الكومة القائم على المصفوفة
• الغربلة للأعلى والغربلة للأسفل
• بناء الكومة في وقت خطي
• الفرز الكومي (heapsort)
• أكوام فيبوناتشي وذات الحدين

Key theories

خاصية الكومة والتمثيل بالمصفوفة

الكومة الثنائية هي شجرة ثنائية شبه كاملة حيث يهيمن مفتاح كل عقدة على مفاتيح أبنائها؛ يمكن تخزينها في مصفوفة بفهرسة ضمنية للأبناء والأجداد، مما يعطي إدراجًا واستخراجًا بكفاءة O(log n) وإيجاد الحد الأدنى بكفاءة O(1).

الكفاءة المخصصة لأكوام فيبوناتشي

تدعم أكوام فيبوناتشي تقليل المفتاح في وقت مخصص O(1) واستخراج الحد الأدنى في وقت مخصص O(log n)، مما يحسن وقت التشغيل التقاربي للخوارزميات مثل دايكسترا وبريم التي تقوم بالعديد من عمليات تقليل المفتاح.

Clinical relevance

تُعد قوائم الانتظار ذات الأولوية بنية تحتية أساسية: فهي ترتب المهام الجاهزة في مجدولات أنظمة التشغيل، وتدير الأحداث في محاكاة الأحداث المنفصلة، وتدفع البحث الأفضل أولاً (best-first) و A*، وتوفر الحدود في خوارزميات دايكسترا وبريم. يوفر الفرز الكومي (Heapsort) فرزًا في مكانه (in-place) بكفاءة O(n log n) مع حدود مضمونة لأسوأ الحالات.

History

قدم ج. و. ج. ويليامز الكومة الثنائية والفرز الكومي (heapsort) في عام 1964، وقدم روبرت فلويد إجراء بناء الكومة في وقت خطي بعد ذلك بوقت قصير. أضافت أكوام ذات الحدين (Vuillemin, 1978) وأكوام فيبوناتشي (Fredman and Tarjan, 1987) دمجًا فعالًا وتقليلًا مخصصًا للمفتاح، مما أدى إلى تحسين أوقات تشغيل خوارزميات الرسوم البيانية الكلاسيكية.

Key figures

• J. W. J. Williams
• Robert W. Floyd
• Michael Fredman
• Robert Tarjan

Seminal works

• williams1964
• fredman1987
• cormen2009

Frequently asked questions

لماذا يتم تخزين الكومة الثنائية في مصفوفة بدلاً من استخدام المؤشرات؟

الكومة الثنائية هي شجرة ثنائية شبه كاملة، لذا فإن عقدها تتوافق بشكل نظيف مع فهارس المصفوفة المتتالية: العقدة في الفهرس i لها أبناء في 2i و 2i+1. هذا يتجنب الحمل الزائد للمؤشرات، ويحسن سلوك ذاكرة التخزين المؤقت (cache)، ويجعل التنقل حسابيًا بسيطًا.

متى تستحق أكوام فيبوناتشي تعقيدها؟

توفر أكوام فيبوناتشي تقليل المفتاح في وقت مخصص O(1)، مما يحسن وقت التشغيل التقاربي للخوارزميات مثل أقصر المسارات لدايكسترا على الرسوم البيانية الكثيفة. عمليًا، تعني عواملها الثابتة الكبيرة أن الأكوام الثنائية الأبسط غالبًا ما تكون أسرع، لذا فهي مهمة بشكل أساسي للحدود النظرية والحالات المتخصصة.