مقدمة
يشير مصطلح “كومة” (Heap) إلى عدة مفاهيم مختلفة في مجالات متنوعة، أبرزها علوم الحاسوب والرياضيات. في هذا المقال، سنستكشف المعاني المتعددة لهذا المصطلح، مع التركيز بشكل خاص على مفهوم كومة البيانات في علم الحاسوب، وهو هيكل بيانات بالغ الأهمية في العديد من الخوارزميات والتطبيقات.
كومة البيانات (Heap Data Structure)
في علم الحاسوب، كومة البيانات هي نوع خاص من هياكل البيانات الشجرية التي تفي بشرط خاصية الكومة. هذه الخاصية تحدد ترتيب العناصر داخل الكومة. هناك نوعان رئيسيان من الكومات:
- كومة دنيا (Min-Heap): في كومة دنيا، قيمة كل عقدة تكون أصغر من أو تساوي قيمة أي من أبنائها. وبالتالي، أصغر عنصر في الكومة يكون دائمًا في الجذر.
- كومة عليا (Max-Heap): في كومة عليا، قيمة كل عقدة تكون أكبر من أو تساوي قيمة أي من أبنائها. وبالتالي، أكبر عنصر في الكومة يكون دائمًا في الجذر.
تعتبر الكومة شجرة ثنائية كاملة أو شبه كاملة، مما يعني أن جميع المستويات ممتلئة بالكامل باستثناء ربما المستوى الأخير، الذي يمتلئ من اليسار إلى اليمين.
خصائص كومة البيانات
تتميز كومة البيانات بعدة خصائص تجعلها هيكل بيانات فعالًا للعديد من التطبيقات:
- الكفاءة: عمليات مثل إدراج عنصر جديد، حذف أصغر/أكبر عنصر (حسب نوع الكومة)، واستعادة أصغر/أكبر عنصر تتم بكفاءة عالية، غالبًا في وقت لوغاريتمي O(log n)، حيث n هو عدد العناصر في الكومة.
- البنية الشجرية: البنية الشجرية تسهل تنظيم البيانات وتنفيذ العمليات عليها بشكل فعال.
- المرونة: يمكن استخدام الكومة لتنفيذ العديد من هياكل البيانات الأخرى، مثل قائمة الأولويات.
العمليات الأساسية على الكومة
تشمل العمليات الأساسية التي يمكن إجراؤها على كومة البيانات ما يلي:
- الإدراج (Insertion): إضافة عنصر جديد إلى الكومة. يتم إضافة العنصر الجديد في البداية إلى المستوى الأخير من الشجرة، ثم يتم “ترشيحه” (Heapify) إلى الأعلى حتى يستقر في مكانه الصحيح وفقًا لخاصية الكومة.
- الحذف (Deletion): حذف أصغر عنصر (في كومة دنيا) أو أكبر عنصر (في كومة عليا). يتم استبدال الجذر (العنصر المراد حذفه) بالعنصر الأخير في المستوى الأخير، ثم يتم حذف العنصر الأخير. بعد ذلك، يتم “ترشيح” الجذر الجديد إلى الأسفل حتى يستقر في مكانه الصحيح.
- الاستعادة (Peek/Find-Min/Find-Max): استعادة أصغر عنصر (في كومة دنيا) أو أكبر عنصر (في كومة عليا) دون حذفه. هذه العملية بسيطة جدًا، حيث أن العنصر المطلوب موجود دائمًا في الجذر.
- الترشيح (Heapify): عملية إعادة ترتيب عناصر الكومة لضمان تحقيق خاصية الكومة. غالبًا ما يتم استخدامها بعد الإدراج أو الحذف.
تطبيقات كومة البيانات
تستخدم كومة البيانات في العديد من الخوارزميات والتطبيقات، بما في ذلك:
- فرز الكومة (Heapsort): خوارزمية فرز فعالة تستخدم هيكل بيانات الكومة لفرز مصفوفة من العناصر. تعتمد هذه الخوارزمية على بناء كومة من المصفوفة الأصلية، ثم استخراج العناصر من الكومة واحدًا تلو الآخر بترتيب معين.
- قائمة الأولويات (Priority Queue): هيكل بيانات مجرد يسمح بإضافة العناصر مع تحديد أولوياتها، واستعادة العنصر ذي الأولوية الأعلى (أو الأقل). يمكن تنفيذ قائمة الأولويات بكفاءة باستخدام كومة البيانات.
- خوارزمية دايجسترا (Dijkstra’s Algorithm): خوارزمية تستخدم لإيجاد أقصر مسار بين عقدتين في رسم بياني. يمكن استخدام كومة البيانات لتحسين كفاءة خوارزمية دايجسترا.
- ضغط البيانات (Data Compression): يمكن استخدام الكومة في بعض خوارزميات ضغط البيانات، مثل ترميز هوفمان.
أنواع أخرى من الكومات
بالإضافة إلى كومات الدنيا والعليا الأساسية، هناك أنواع أخرى أكثر تعقيدًا من الكومات، مثل:
- الكومة الثنائية (Binary Heap): الكومة الأكثر شيوعًا، حيث لكل عقدة طفلان على الأكثر.
- الكومة ذات الحدين (Binomial Heap): عبارة عن مجموعة من أشجار ذات حدين تفي بخصائص معينة.
- كومة فيبوناتشي (Fibonacci Heap): هيكل بيانات أكثر تعقيدًا يوفر أداءً أفضل في بعض العمليات مقارنة بالكومة الثنائية أو الكومة ذات الحدين.
مقارنة بين الكومة وشجرة البحث الثنائية (BST)
غالبًا ما تتم مقارنة الكومة بشجرة البحث الثنائية (BST)، وهما هيكلا بيانات شجريان مختلفان. على الرغم من وجود تشابهات بينهما، إلا أنهما يختلفان في عدة جوانب رئيسية:
- الترتيب: في شجرة البحث الثنائية، يتم ترتيب العناصر بحيث تكون جميع العناصر الموجودة في الشجرة الفرعية اليسرى لعقدة ما أصغر من قيمة العقدة، وجميع العناصر الموجودة في الشجرة الفرعية اليمنى أكبر من قيمة العقدة. في الكومة، يتم ترتيب العناصر فقط فيما يتعلق بالعقدة الأب.
- الغرض: تستخدم شجرة البحث الثنائية بشكل أساسي للبحث عن العناصر وإدراجها وحذفها بترتيب معين. تستخدم الكومة بشكل أساسي للعثور على أصغر/أكبر عنصر وإزالته بكفاءة.
- الشكل: شجرة البحث الثنائية يمكن أن تكون غير متوازنة، مما يؤدي إلى أداء أسوأ في بعض العمليات. الكومة هي دائمًا شجرة كاملة أو شبه كاملة، مما يضمن أداءً جيدًا.
تنفيذ الكومة
يمكن تنفيذ الكومة باستخدام مصفوفة أو قائمة مرتبطة. التنفيذ باستخدام مصفوفة هو الأكثر شيوعًا لأنه يوفر وصولاً فعالاً إلى العناصر الأبناء والأباء. يمكن حساب فهرس الابن الأيسر والأيمن لعقدة في المصفوفة باستخدام الصيغ التالية:
- الابن الأيسر: 2 * i + 1
- الابن الأيمن: 2 * i + 2
حيث i هو فهرس العقدة الأب في المصفوفة. يمكن حساب فهرس الأب لعقدة في المصفوفة باستخدام الصيغة التالية:
- الأب: (i – 1) / 2
لاحظ أن القسمة هنا هي قسمة عدد صحيح، مما يعني تجاهل الجزء العشري.
اعتبارات الأداء
يعتمد أداء عمليات الكومة على نوع الكومة وحجم البيانات. بشكل عام، توفر الكومة الثنائية أداءً جيدًا لمعظم التطبيقات. ومع ذلك، في بعض الحالات، قد تكون الكومة ذات الحدين أو كومة فيبوناتشي أكثر كفاءة.
أهمية فهم الكومة
فهم هيكل بيانات الكومة أمر ضروري لعلماء الحاسوب ومهندسي البرمجيات. إنها أداة قوية يمكن استخدامها لحل مجموعة واسعة من المشكلات بكفاءة. بالإضافة إلى ذلك، فإن فهم الكومة يساعد على فهم هياكل البيانات والخوارزميات الأخرى الأكثر تعقيدًا.
خاتمة
الكومة هي هيكل بيانات متعدد الاستخدامات وفعال يستخدم في العديد من التطبيقات في علوم الحاسوب. سواء كنت تقوم بفرز البيانات، أو تنفيذ قائمة أولويات، أو البحث عن أقصر مسار، فإن فهم الكومة يمكن أن يساعدك في كتابة تعليمات برمجية أكثر كفاءة وفعالية. من خلال فهم خصائصها وأنواعها المختلفة وتطبيقاتها، يمكنك الاستفادة من قوة هذا الهيكل البياني لحل المشكلات المعقدة.