تُعدّ قائمة الأولويات (Priority Queue) بنية بيانات أساسية توسّع وظائف قائمة الانتظار القياسية عن طريق تعيين أولوية لكل عنصر. على عكس قائمة FIFO (الاولوية للدخول الأول، والخروج الأول) حيث يتمّ معالجة العناصر بالترتيب الذي وصلت به، تقوم قائمة الأولويات بإزالة العناصر بناءً على أولويتها. يتمّ دائمًا معالجة العنصر ذي الأولوية الأعلى أولاً. يمكن أن تعتمد هذه الأولوية على القيمة العددية (الأصغر أو الأكبر)، أو أي معايير مقارنة مخصصة.
تُعتبر قوائم الأولويات ذات قيمة كبيرة في العديد من الخوارزميات والتطبيقات حيث يكون إدارة المهام أو الأحداث بكفاءة بناءً على الأهمية أمرًا بالغ الأهمية. تشمل الأمثلة:
- جدولة أقصر مهمة أولاً (SJF): في أنظمة التشغيل، جدولة العمليات بكفاءة بناءً على وقت التنفيذ المقدر.
- خوارزميات البحث الأفضل أولاً (A*، Dijkstra): إيجاد المسارات المثلى في الرسوم البيانية عن طريق إعطاء الأولوية للعقد بناءً على المسافة المقدرة من الهدف.
- محاكاة الأحداث: إدارة الأحداث في محاكاة الأحداث المنفصلة، مع ضمان معالجة الأحداث الأكثر إلحاحًا أولاً.
- فرز الكومة (Heap Sort): خوارزمية فرز تستفيد من خصائص الكومة (نوع متخصص من قائمة الأولويات) للفرز بكفاءة.
- ترميز هوفمان (Huffman Coding): إنشاء خوارزميات ضغط فعالة عن طريق إعطاء الأولوية للرموز بناءً على ترددها.
تنفيذ قوائم الأولويات في C#
يوفر C# عدة طرق لتنفيذ قائمة الأولويات. دعونا نستكشف طريقتين شائعتين:
1. استخدام SortedSet
توفر فئة SortedSet المدمجة طريقة ملائمة لتنفيذ قائمة الأولويات. تحافظ SortedSet تلقائيًا على عناصرها بترتيب مرتب، مما يبسط عملية تحديد الأولويات. هذا مفيد بشكل خاص عندما يتم تحديد الأولوية ضمنيًا من خلال الترتيب الطبيعي للعناصر (مثل الأعداد الصحيحة).
using System;
using System.Collections.Generic;
public class PriorityQueueSortedSet<T> where T : IComparable<T>
{
private SortedSet<T> _elements = new SortedSet<T>();
public void Enqueue(T item) => _elements.Add(item);
public T Dequeue()
{
if (_elements.Count == 0)
{
throw new InvalidOperationException("Priority queue is empty.");
}
T item = _elements.Min;
_elements.Remove(item);
return item;
}
public bool IsEmpty() => _elements.Count == 0;
public int Count => _elements.Count;
}
هذا التنفيذ بسيط، لكن أدائه محدود بواسطة SortedSet الأساسية، والتي توفر تعقيدًا قدره O(log n) لعمليات الإضافة والإزالة. قد يكون استخدام الذاكرة أيضًا مرتفعًا نسبيًا، خاصةً بالنسبة للمجموعات الكبيرة من البيانات.
2. تنفيذ كومة الحد الأدنى (Min-Heap)
للحصول على أداء محسّن، خاصةً مع مجموعات البيانات الكبيرة، يوفر تنفيذ مخصص لكومة الحد الأدنى مزايا كبيرة. كومة الحد الأدنى هي بنية شجرة ثنائية تضمن دائمًا أن يكون أصغر عنصر في الجذر، مما يمكّن من تعقيد O(log n) لكل من عمليات الإضافة والإزالة. على الرغم من أنّه أكثر تعقيدًا في التنفيذ من SortedSet، إلا أن كومة الحد الأدنى توفر أداءً أفضل وتحكمًا دقيقًا في إدارة الذاكرة.
(إن تنفيذ مفصل لكومة الحد الأدنى يتجاوز نطاق هذه المقالة، ولكن تتوفر العديد من الموارد عبر الإنترنت).
مقارنة التنفيذات
| الميزة | SortedSet |
كومة الحد الأدنى |
|---|---|---|
| سهولة الاستخدام | أسهل | أكثر صعوبة |
| أداء الإضافة/الإزالة | O(log n) | O(log n) |
| استخدام الذاكرة | ربما أعلى | ربما أقل |
| المرونة | أقل | أكثر |
اختيار التنفيذ المناسب
يعتمد الخيار الأمثل بين SortedSet وكومة الحد الأدنى المخصصة على متطلباتك المحددة. SortedSet مثالي للتطبيقات البسيطة حيث تتفوق سهولة التنفيذ على الحاجة إلى الأداء العالي. بالنسبة للتطبيقات الحرجة من حيث الأداء أو مجموعات البيانات الكبيرة، يوفر تنفيذ كومة الحد الأدنى المخصصة مزايا كبيرة في السرعة وكفاءة الذاكرة.