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

Question

هل من الممكن تنفيذ قائمة انتظار ذات أولوية فعالة (كفاءة كهامة) فقط باستخدام هيكل بيانات المكدس؟

الكفاءة المعتادة لقائمة انتظار أولوية يتم تنفيذها باستخدام كومة هي:

• الحصول على دقيقة - $ O (1) $
• استخراج دقيقة - $ o (\ log n) $
• إضافة - $ o (\ log n) $

هل سيكون من الممكن القيام بشيء مع نفس التعقيد باستخدام كدسات فقط؟

أريد تنفيذ A * (والذي يستخدم قائمة انتظار أولوية لتحديد أولويات العقد) كجوارق مسارات داخل MINECRAFT، لكن ماين كرافت لا يسمح بالوصول العشوائي، والهيكل الديناميكي الأكثر فعالية التي يمكن تنفيذها فيها هي مكدس.

Answer 1

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

Answer 2

يمكنك القيام بمثل هذا التمثيل المثالي لقوائم الانتظار ذات الأولوية باستخدام (Binary) بنية البيانات، باستخدامه، يمكنك تطبيق مكدسات وطوابين ...

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

يمكنك العثور على كل هذا في Cormen et al.، مقدمة في الخوارزميات، الطبعة الثالثة.

حسنا، ينطبق تنفيذ قوائم الانتظار ذات الأولوية باستخدام خصائص الكومة، max_heap أو min_heap حتى min_priority_queue يمكن تطبيق min_priority_queue باستخدام min_heap باستخدام الإجراءات المستخدمة للحصول على أكوام مثل build_heap () أولا، max_heapify ()، zill_key ()والإدراج والحذف.

لاحظ أن الكومة (الثنائية) هي كائن صفيف يمكن أن يظهر كشجرة بحث ثنائية كاملة تقريبا ...

لتنفيذ المكدس (هناك رمز PSudo)

giveacodicetagpre.

لتنفيذ قائمة الانتظار باستخدام قائمة انتظار الأولوية (كومة الكومة) نفسها ولكن الأولوية تنخفض واحدة تلو الأخرى.