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

في علوم الحاسوب ، يُعدّ طابور الأولوية الرتيب نوعًا من أنواع بيانات طابور الأولوية المجردة ، حيث يُشترط أن تُشكّل أولويات العناصر المُستخرجة تسلسلًا رتيبًا . أي، بالنسبة لطابور أولوية يكون فيه كل عنصر مُستخرج تباعًا هو العنصر ذو الأولوية الدنيا (كومة دنيا)، يجب أن تكون الأولوية الدنيا متزايدة بشكل رتيب. وعلى العكس، بالنسبة لكومة عظمى، يجب أن تكون الأولوية القصوى متناقصة بشكل رتيب. ينشأ افتراض الرتابة بشكل طبيعي في العديد من تطبيقات طوابير الأولوية، ويمكن استخدامه كفرضية مُبسّطة لتسريع أنواع مُعينة من طوابير الأولوية. ^[¹^]^:¹²⁸

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

التطبيقات

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

في خوارزمية ديكسترا لحل مشكلة أقصر مسار ، تُستخرج رؤوس الرسم البياني الموزون المعطى بترتيب تصاعدي حسب بُعدها عن رأس البداية، ويُستخدم طابور ذو أولوية لتحديد أقرب رأس متبقٍ إلى رأس البداية. لذا، في هذا التطبيق، تكون عمليات الطابور ذي الأولوية رتيبة.

وبالمثل، في خوارزميات خطوط المسح في الهندسة الحسابية ، تُعطى الأولوية للأحداث التي يتقاطع فيها خط المسح مع نقطة معينة بناءً على إحداثيات تلك النقطة، وتُستخرج هذه الأحداث بترتيب رتيب. ويظهر ترتيب الاستخراج الرتيب أيضًا في نسخة "الأفضل أولًا" من خوارزمية التفرع والتقييد . ^{[ 1 ]}^{: 128}

هياكل البيانات

أي طابور أولوية قادر على التعامل مع عمليات الاستخراج غير الرتيبة قادر أيضًا على التعامل مع عمليات الاستخراج الرتيبة، ولكن بعض طوابير الأولوية مُخصصة للعمل فقط مع عمليات الاستخراج الرتيبة أو تعمل بكفاءة أكبر عند استخدامها. على سبيل المثال، طابور الدلو هو بنية بيانات بسيطة لطابور الأولوية، ويتكون من مصفوفة مُفهرسة حسب الأولوية، حيث تحتوي كل خلية في المصفوفة على دلو من العناصر بتلك الأولوية. تُجري عملية استخراج الحد الأدنى بحثًا تسلسليًا عن أول دلو غير فارغ، ثم تختار عنصرًا عشوائيًا من ذلك الدلو. بالنسبة لعمليات الاستخراج غير الرتيبة، تستغرق كل عملية استخراج الحد الأدنى وقتًا (في أسوأ الحالات) يتناسب مع طول المصفوفة (عدد الأولويات المختلفة). مع ذلك، عند استخدامها كطابور أولوية رتيب، يمكن أن يبدأ البحث عن الدلو التالي غير الفارغ من أولوية آخر عملية استخراج حد أدنى سابقة، بدلًا من بداية المصفوفة. يؤدي هذا التحسين إلى جعل إجمالي الوقت اللازم لتنفيذ سلسلة من العمليات متناسبًا مع مجموع عدد العمليات وطول المصفوفة، بدلاً من (كما هو الحال في الحالة غير الرتيبة) حاصل ضرب هاتين الكميتين. ^{[ 2 ]}

وصف تشيركاسكي، وغولدبيرغ، وسيلفرشتاين (1999) مخططًا أكثر تعقيدًا يُسمى طابور "الكومة العلوية" (HOT) لطوابير الأولوية الرتيبة ذات الأولويات الصحيحة، ويعتمد على التجميع متعدد المستويات مع طابور أولوية الكومة التقليدي. باستخدام هذه الطريقة، حصلوا على بنية يمكنها الاحتفاظ بالعناصر ذات الأولويات الصحيحة في نطاق من $0$ إلى قيمة مُعاملة $C.$ يستخدم طابور "الكومة العلوية" وقتًا ثابتًا لكل عملية إدخال أو إنقاص أولوية، بالإضافة إلى الوقت المُستهلك. $O((\log C)^{1/3}(\log \log C)^{1/2})$ لكل عملية استخراج-أدنى. ^{[ 3 ]} يسمح هيكل آخر ذو صلة من تصميم رامان (1996) بأن تكون الأولويات أعدادًا صحيحة للآلة، ويسمح أيضًا بعمليات إدخال وتخفيض الأولوية في وقت ثابت، مع عمليات استخراج-أدنى على قائمة انتظار ذات أولوية مكونة من $n$ عنصرًا تستغرق وقتًا مستهلكًا $O({\sqrt {\log n\log \log n}})$ [ ⁴^] تؤدي هذه النتائج إلى تسريع مماثل في خوارزمية ديكسترا للرسوم البيانية ذات أوزان الحواف الصحيحة ^.

مراجع

1 2 ميلهورن، كورت ؛ ساندرز، بيتر (2008). "قوائم الانتظار ذات الأولوية" (ملف PDF) . الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية . سبرينغر.
↑ سكينا، ستيفن س. (1998)، دليل تصميم الخوارزميات ، سبرينغر، ص 181، ISBN 978-0-387-94860-7.
↑ تشيركاسكي، بوريس ف.؛ غولدبيرغ، أندرو ف .؛ سيلفرشتاين، كريغ (أغسطس 1999)، "الدلاء، والأكوام، والقوائم، وقوائم الانتظار ذات الأولوية الرتيبة"، مجلة SIAM للحوسبة ، 28 (4): 1326-1346 (إلكتروني)، CiteSeerX 10.1.1.49.8244 ، doi : 10.1137/S0097539796313490 ، MR 1681014 .
↑ رامان، راجيف (1996)، "طوابير الأولوية: الصغيرة، والرتيبة، والمتشعبة"، الخوارزميات - ESA '96 (برشلونة) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1136، برلين: سبرينغر، الصفحات 121-137 ، doi : 10.1007/3-540-61680-2_51 ، ISBN 978-3-540-61680-1، MR 1469229 ، S2CID 17004419 .

[mehlhorn-1] 1 2 ميلهورن، كورت ؛ ساندرز، بيتر (2008). "قوائم الانتظار ذات الأولوية" (ملف PDF) . الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية . سبرينغر.

[2] سكينا، ستيفن س. (1998)، دليل تصميم الخوارزميات ، سبرينغر، ص 181، ISBN 978-0-387-94860-7.

[3] تشيركاسكي، بوريس ف.؛ غولدبيرغ، أندرو ف .؛ سيلفرشتاين، كريغ (أغسطس 1999)، "الدلاء، والأكوام، والقوائم، وقوائم الانتظار ذات الأولوية الرتيبة"، مجلة SIAM للحوسبة ، 28 (4): 1326-1346 (إلكتروني)، CiteSeerX 10.1.1.49.8244 ، doi : 10.1137/S0097539796313490 ، MR 1681014 .

[4] رامان، راجيف (1996)، "طوابير الأولوية: الصغيرة، والرتيبة، والمتشعبة"، الخوارزميات - ESA '96 (برشلونة) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1136، برلين: سبرينغر، الصفحات 121-137 ، doi : 10.1007/3-540-61680-2_51 ، ISBN 978-3-540-61680-1، MR 1469229 ، S2CID 17004419 .

[

[ 2 ]

[ 3 ]

4