قائمة انتظار الأولوية باستخدام المكدس

Question

هل يمكن لأحد بناء قائمة انتظار أولوية باستخدام مكدسات، بحيث تحتوي قائمة انتظار الأولوية على نفس التعقيد لكل عملية. هل يمكن القيام به؟إذا كان الأمر كذلك كيف؟إن لم يكن ما هو أفضل حل يمكن القيام به؟

كل عملية كومة باستخدام صفيف هي $ O (1) $ في حين أن جميع عمليات قائمة انتظار الأولوية تقريبا هي $ O (logn) $ . يمكن تنفيذ التنفيذ باستخدام $ 2D $ codacks، كل عناصر من المكدس مرة أخرى كومة. عندما يكون العنصر الأول من المكدس الرئيسي هو العنصر الأول من المداخن الأخرى. سيستغرق عملية Dequeue $ O (n) $ كما هو lifo و قائمة انتظار الأولوية هو FIFO.

Answer 1

فكر في الأمر.يمكنك فرز صفيف بإضافة جميع العناصر إلى قائمة انتظار أولوية، ثم إزالة العناصر في الترتيب الفرز.

إذا كنت تستطيع تشغيل قائمة انتظار أولوية في وقت ثابت، يمكنك الفرز في الوقت الخطي.لكنك لا تستطيع ذلك.