طابور الدلو

يمكن لطابور الحاويات التعامل مع عناصر ذات أولويات عددية صحيحة تتراوح من 0 أو 1 حتى حدٍّ معروف C ، بالإضافة إلى عمليات إدراج العناصر، وتغيير أولوياتها، واستخراج (إيجاد وإزالة) العنصر ذي الأولوية الدنيا (أو القصوى). يتكون الطابور من مصفوفة A من هياكل بيانات حاويات ؛ في معظم المصادر، تكون هذه الحاويات عبارة عن قوائم مرتبطة ثنائياً، ولكن يمكن أن تكون بدلاً من ذلك مصفوفات ديناميكية ^{[ 3 ]} أو مجموعات ديناميكية . تخزن الحاوية الموجودة في الخلية p من المصفوفة A [ p ] مجموعة العناصر التي لها الأولوية p .

يمكن لقائمة انتظار الحاويات التعامل مع العمليات التالية:

• لإدراج عنصر x ذي أولوية p ، أضف x إلى الحاوية في A [ p ] .
• لتغيير أولوية عنصر ما، قم بإزالته من الحاوية لأولويته القديمة وأعد إدخاله في الحاوية لأولويته الجديدة.
• لاستخراج عنصر ذي أولوية دنيا أو قصوى، قم بإجراء بحث تسلسلي في المصفوفة للعثور على الحاوية الأولى أو الأخيرة غير الفارغة، على التوالي، واختر عنصرًا عشوائيًا من هذه الحاوية، وقم بإزالته من الحاوية.

وبهذه الطريقة، تستغرق عمليات الإضافة وتغييرات الأولوية وقتًا ثابتًا، ويستغرق استخراج عنصر الأولوية الأدنى أو الأقصى وقتًا قدره O ( C ) . ^{[ 1 ] [ 6 ] [ 8 ]}

كتحسين للأداء، يمكن لبنية البيانات أن تبدأ كل عملية بحث تسلسلي عن عنصر غير فارغ من آخر عنصر غير فارغ تم العثور عليه، بدلاً من بداية المصفوفة. يمكن تحقيق ذلك بطريقتين: البحث المؤجل (تأجيل عمليات البحث التسلسلي حتى الحاجة إليها) أو البحث المسبق (إجراء عمليات البحث مسبقًا). يؤثر اختيار وقت إجراء البحث على عمليات بنية البيانات التي تتأثر سلبًا بهذه العمليات. استخدمت النسخة الأصلية من بنية Dial البحث المؤجل. يتم ذلك عن طريق الاحتفاظ بفهرس L يمثل الحد الأدنى لأولوية أي عنصر موجود حاليًا في قائمة الانتظار. عند إدراج عنصر جديد، يجب تحديث L إلى الحد الأدنى بين قيمته القديمة وأولوية العنصر الجديد. عند البحث عن العنصر ذي الأولوية الدنيا، يمكن أن يبدأ البحث من L بدلاً من الصفر، وبعد انتهاء البحث، يجب أن يبقى L مساويًا للأولوية التي تم العثور عليها. ^{[ 7 ] [ 9 ]} بدلاً من ذلك، يُبقي الإصدار المُستعجل من هذا التحسين قيمة L مُحدَّثة بحيث تُشير دائمًا إلى أول خانة غير فارغة. عند إدراج عنصر جديد ذي أولوية أقل من L ، تُعيِّن بنية البيانات قيمة L إلى الأولوية الجديدة، وعند إزالة العنصر الأخير من خانة ذات أولوية L ، تُجري بحثًا تسلسليًا عبر الفهارس الأكبر حجمًا حتى العثور على خانة غير فارغة، وتُعيِّن قيمة L إلى أولوية الخانة الناتجة. ^{[ 1 ]}

في كلا هذين الشكلين، يستغرق كل بحث تسلسلي وقتًا يتناسب مع الفرق بين القيمتين القديمة والجديدة لـ L. قد يكون هذا أسرع بكثير من الحد الزمني O ( C ) لعمليات البحث في النسخة غير المُحسَّنة من بنية البيانات. في العديد من تطبيقات قوائم الانتظار ذات الأولوية، مثل خوارزمية ديكسترا ، تُشكِّل الأولويات الدنيا متتالية رتيبة ، مما يسمح باستخدام قائمة انتظار ذات أولوية رتيبة . في هذه التطبيقات، بالنسبة لكلٍّ من الشكلين الكسول والسريع للبنية المُحسَّنة، تغطي عمليات البحث التسلسلي عن الحاويات غير الفارغة نطاقات منفصلة من الحاويات. ولأن كل حاوية تقع في نطاق واحد على الأكثر من هذه النطاقات، فإن مجموع عدد خطواتها لا يتجاوز C. لذلك، في هذه التطبيقات، يكون إجمالي الوقت لتسلسل من n عملية هو O ( n + C ) ، بدلًا من الحد الزمني الأبطأ O ( nC ) الذي كان سينتج بدون هذا التحسين. ^{[ 9 ]} يمكن تطبيق تحسين مماثل في التطبيقات التي تستخدم طابورًا ذا دلو للعثور على العناصر ذات الأولوية القصوى، ولكن في هذه الحالة يجب أن يحتفظ بفهرس يحدد الحد الأعلى للأولوية القصوى، ويجب أن يبدأ البحث التسلسلي عن دلو غير فارغ من هذا الحد الأعلى نزولًا. ^{[ 10 ]}

يمكن استخدام تحسين آخر (سبق أن ذكره ديال عام 1969 ) لتوفير المساحة عندما تكون الأولويات رتيبة، وتقع طوال مسار الخوارزمية ضمن نطاق من قيم r بدلاً من امتدادها على النطاق الكامل من 0 إلى C. في هذه الحالة، يمكن فهرسة المصفوفة باستخدام الأولويات بتردد r بدلاً من قيمها الفعلية. يجب أن يبدأ البحث عن عنصر الأولوية الأدنى دائمًا من الحد الأدنى السابق، لتجنب الأولويات الأعلى من الحد الأدنى ولكن بترددات أقل. على وجه الخصوص، يمكن تطبيق هذه الفكرة في خوارزمية ديكسترا على الرسوم البيانية التي تكون أطوال حوافها أعدادًا صحيحة في النطاق من 1 إلى r . ^{[ 8 ]}

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

على سبيل المثال، لنفترض وجود طابور ذي أربع أولويات، وهي الأرقام 0 و1 و2 و3. يتكون هذا الطابور من مصفوفة.${\displaystyle A}$تحتوي كل خلية من خلاياها الأربع على مجموعة من العناصر، تكون فارغة في البداية. لأغراض هذا المثال،${\displaystyle A}$يمكن كتابتها كسلسلة بين قوسين من أربع مجموعات:${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}$لنفترض سلسلة من العمليات التي نقوم فيها بإدخال عنصرين${\displaystyle x}$و${\displaystyle y}$بنفس الأولوية 1، أضف عنصرًا ثالثًا${\displaystyle z}$مع الأولوية 3، قم بتغيير أولوية${\displaystyle x}$إلى 3، ثم قم بإجراء عمليتي استخراج للعنصر ذي الأولوية الدنيا.

• بعد الإدخال${\displaystyle x}$مع إعطاء الأولوية رقم 1،${\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}$.
• بعد الإدخال${\displaystyle y}$مع إعطاء الأولوية رقم 1،${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}$.
• بعد إدخال الحرف z بالأولوية 3،${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}$.
• تغيير أولوية x من 1 إلى 3 يتضمن إزالته من${\displaystyle A[1]}$وإضافته إلى${\displaystyle A[3]}$وبعد ذلك${\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}$.
• في النسخة الأساسية من قائمة الانتظار، يتم استخراج العنصر ذي الأولوية الدنيا، ويتم البحث بدءًا من بداية${\displaystyle A}$لإيجاد أول عنصر غير فارغ فيه:${\displaystyle A[0]}$فارغ لكن${\displaystyle A[1]=\{y\}}$، وهي مجموعة غير فارغة. يختار عنصرًا عشوائيًا من هذه المجموعة (العنصر الوحيد،${\displaystyle y}$) كعنصر ذي أولوية دنيا. إزالة${\displaystyle y}$من أوراق الهيكل${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}$.
• أما عملية الاستخراج الثانية، في النسخة الأساسية من قائمة الانتظار، فتبحث مرة أخرى من بداية المصفوفة:${\displaystyle A[0]=\emptyset }$،${\displaystyle A[1]=\emptyset }$،${\displaystyle A[2]=\emptyset }$،${\displaystyle A[3]={}}$غير فارغ. في النسخ المحسّنة من قائمة الانتظار ذات الدلو، يبدأ هذا البحث بدلاً من ذلك من آخر موضع تم العثور عليه غير فارغ.${\displaystyle A[1]}$في كلتا الحالتين،${\displaystyle A[3]=\{x,z\}}$تُعتبر المجموعة الأولى غير الفارغة. يتم اختيار أحد عناصرها بشكل عشوائي كعنصر ذي أولوية دنيا؛ على سبيل المثال،${\displaystyle z}$قد يتم اختيار هذا العنصر. يتم إزالة هذا العنصر، تاركًا${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}$.

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

في خوارزمية ديكسترا لإيجاد أقصر المسارات في الرسوم البيانية الموجهة ذات أوزان الحواف الموجبة، تكون الأولويات رتيبة، ^{[ 13 ]} ويمكن استخدام طابور دلو رتيب للحصول على حد زمني قدره O ( m + dc ) ، حيث m هو عدد الحواف، وd هو قطر الشبكة، و c هو الحد الأقصى لتكلفة الرابط (عدد صحيح). ^{[ 9 ] [ 14 ]} يُعرف هذا النوع من خوارزمية ديكسترا أيضًا باسم خوارزمية ديال ، ^{[ 9 ]} نسبةً إلى روبرت ب. ديال، الذي نشرها عام 1969. ^{[ 7 ]} تعمل الفكرة نفسها أيضًا، باستخدام طابور دلو مُكمّم، للرسوم البيانية ذات أوزان الحواف الحقيقية الموجبة عندما تكون نسبة الوزن الأقصى إلى الوزن الأدنى على الأكثر c . ^{[ 15 ]} في هذه النسخة الكمية من الخوارزمية، تُعالَج الرؤوس بترتيبٍ مختلف عن النتيجة باستخدام قائمة انتظار ذات أولوية غير كمية، ولكن لا يزال يتم العثور على أقصر المسارات الصحيحة. ^{[ 5 ]} في هذه الخوارزميات، لا تتجاوز الأولويات نطاق عرضه c + 1 ، لذا يمكن استخدام التحسين المعياري لتقليل المساحة إلى O ( n + c ) . ^{[ 8 ] [ 14 ]}

يمكن استخدام صيغة معدلة من الخوارزمية نفسها لحل مشكلة المسار الأوسع . وبالاقتران مع طرق لتقسيم أوزان الحواف غير الصحيحة بسرعة إلى مجموعات فرعية يمكن تعيين أولويات صحيحة لها، فإنها تؤدي إلى حلول شبه خطية لنسخة المصدر الواحد والوجهة الواحدة من مشكلة المسار الأوسع. ^{[ 16 ]}

تُدخل مسألة تغطية المجموعات عائلة من المجموعات . يجب أن يكون الناتج عائلة فرعية من هذه المجموعات، بنفس اتحاد العائلة الأصلية، مع تضمين أقل عدد ممكن من المجموعات. تُصنف هذه المسألة ضمن المسائل الصعبة حسابيًا (NP-hard) ، ولكن يوجد لها خوارزمية تقريبية جشعة تحقق نسبة تقريب لوغاريتمية، وهي أفضل نسبة ممكنة ما لم تكن P = NP . ^{[ 17 ]} تختار هذه الخوارزمية التقريبية عائلتها الفرعية عن طريق اختيار مجموعة بشكل متكرر تغطي أكبر عدد ممكن من العناصر المتبقية غير المغطاة. ^{[ 18 ]} يتطلب تمرين قياسي في تصميم الخوارزميات تنفيذ هذه الخوارزمية في وقت خطي بالنسبة لحجم المدخلات، وهو مجموع أحجام جميع مجموعات المدخلات. ^{[ 19 ]}

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

يمكن استخدام قوائم الانتظار المجمعة لجدولة المهام ذات المواعيد النهائية، على سبيل المثال في إعادة توجيه حزم بيانات الإنترنت مع ضمانات جودة الخدمة . في هذا التطبيق، يجب تقسيم المواعيد النهائية إلى فترات زمنية منفصلة، ​​وتُعتبر المهام التي تقع مواعيدها النهائية ضمن نفس الفترة الزمنية متساوية الأولوية. ^{[ 2 ]}

تم تطبيق نوع مُعدّل من بنية بيانات قائمة الانتظار المُكمّمة، وهي قائمة انتظار التقويم ، على جدولة عمليات محاكاة الأحداث المنفصلة ، ​​حيث تمثل عناصر قائمة الانتظار أحداثًا مستقبلية مُرتبة حسب توقيت حدوثها خلال المحاكاة. في هذا التطبيق، يُعد ترتيب الأحداث بالغ الأهمية، لذا لا يمكن تقريب الأولويات. لذلك، تُجري قائمة انتظار التقويم عمليات البحث عن العنصر ذي الأولوية الدنيا بطريقة مختلفة عن قائمة انتظار الدلو: ففي قائمة انتظار الدلو، يُمكن إرجاع أي عنصر من الدلو الأول غير الفارغ، بينما تبحث قائمة انتظار التقويم في جميع العناصر الموجودة في ذلك الدلو لتحديد العنصر ذي الأولوية الأقل غير المُكمّمة. وللحفاظ على سرعة عمليات البحث هذه، تحاول هذه النسخة المُعدّلة الحفاظ على عدد الدلو متناسبًا مع عدد العناصر، وذلك عن طريق تعديل مقياس التكميم وإعادة بناء بنية البيانات عند اختلال توازنها. قد تكون قوائم انتظار التقويم أبطأ من قوائم انتظار الحاويات في أسوأ الحالات (عندما تتجمع عناصر كثيرة في أصغر حاوية واحدة)، لكنها سريعة عندما تتوزع العناصر بالتساوي بين الحاويات، مما يجعل متوسط ​​حجم الحاوية ثابتًا. ^{[ 20 ] [ 21 ]}

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