رتل اولوية

في علوم الكمبيوتر، قائمة الانتظار ذات الأولوية بالانجليزية Priority Queue هي نوع بيانات تجريدي يشبه قائمة الانتظار العادية أو بنية البيانات المكدسة. كل عنصر في قائمة انتظار الأولوية له أولوية مرتبطة به. في قائمة انتظار الأولوية، يتم تقديم العناصر ذات الأولوية العالية قبل العناصر ذات الأولوية المنخفضة. في بعض التطبيقات، إذا كان لعنصرين نفس الأولوية، فسيتم تقديمهما بنفس الترتيب الذي تم إدراجهما به. في تطبيقات أخرى، ترتيب العناصر التي لها نفس الأولوية غير محدد.

على الرغم من أن قوائم الانتظار ذات الأولوية غالبًا ما يتم تنفيذها باستخدام الكومة ، إلا أنها تختلف من الناحية النظرية عن الكومة. قائمة انتظار الأولوية عبارة عن بنية بيانات مجردة مثل القائمة أو الخريطة، تمامًا كما يمكن تنفيذ القائمة باستخدام قائمة مرتبطة أو باستخدام مصفوفة ، يمكن تنفيذ قائمة انتظار ذات أولوية باستخدام كومة أو طريقة أخرى مثل مصفوفة غير مرتبة.

العمليات على الرتل

يجب أن تدعم قائمة الانتظار ذات الأولوية العمليات التالية على الأقل:

  • is_empty : تحقق مما إذا كانت قائمة الانتظار لا تحتوي على عناصر.
  • Insert_with_priority : إضافة عنصر إلى قائمة الانتظار ذات الأولوية المرتبطة به.
  • pull_highest_priority_element : إزالة العنصر الذي له الأولوية القصوى من قائمة الانتظار وإعادته.
    يُعرف هذا أيضًا باسم " pop_element(Off) " أو " get_maximum_element " أو " get_front(most)_element ".
    تعكس بعض الاتفاقيات ترتيب الأولويات، معتبرا القيم الأقل أولوية أعلى، لذلك قد يُعرف هذا أيضًا باسم " get_minimum_element "، وغالبًا ما يشار إليه باسم " get-min " في الأدبيات.
    قد يتم تحديد ذلك بدلاً من ذلك كوظيفتين منفصلتين " peek_at_highest_priority_element " و" delete_element "، واللتين يمكن دمجهما لإنتاج " pull_highest_priority_element "
    بالإضافة إلى ذلك، فإن peek (في هذا السياق يُطلق عليه غالبًا find-max أو find-min ) ، والذي يُرجع العنصر ذو الأولوية الأعلى ولكنه لا يعدل قائمة الانتظار، يتم تنفيذه بشكل متكرر جدًا، ويتم تنفيذه دائمًا تقريبًا في وقت O (1) . تعد هذه العملية وأدائها O (1) أمرًا بالغ الأهمية للعديد من تطبيقات قوائم الانتظار ذات الأولوية.

قد تدعم التطبيقات الأكثر تقدمًا عمليات أكثر تعقيدًا، مثل pull_lowest_priority_element ، وفحص العناصر القليلة الأولى ذات الأولوية الأعلى أو الأدنى، ومسح قائمة الانتظار، ومسح مجموعات فرعية من قائمة الانتظار، وإجراء إدراج دفعي، ودمج طابورتين أو أكثر في قائمة انتظار واحدة، وزيادة الأولوية من أي عنصر الخ

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

تحقيق الخوارزمية

هنالك مجموعة متنوعة من الطرق البسيطة، وغير الفعالة عادةً، لتنفيذ قائمة الانتظار ذات الأولوية. أنها توفر تشبيهًا لمساعدة الشخص على فهم ماهية قائمة الانتظار ذات الأولوية.

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

insert(node)
{
    list.append(node)
}

pull()
{
    highest = list.get_first_element()
    foreach node in list
    {
        if highest.priority < node.priority
        {
            highest = node
        }
    }
    list.remove(highest)
    return highest
}

insert(node) 

{insert (node
    foreach (index, element) in list
    {
        if node.priority < element.priority
        {
            list.insert_at_index(node,index)
            break
        }
    }
}

pull()
{
    highest = list.get_at_index(list.length-1)
    list.remove(highest)
    return highest
}