كومة ثنائية مقابل كومة ذات حدين مقابل كومة فيبوناتشي ، فيما يتعلق بأداء قائمة انتظار ذات أولوية

Question

هل يمكن لشخص ما أن يشرح لي كيف يمكنني أن أقرر ما إذا كنت سأستخدم تنفيذ كومة واحد أو آخر ، من بين تلك المذكورة في العنوان؟

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

هناك شيء آخر يجب مراعاته وهو أنني أستخدم haskell هذه المرة ، لذا ، إذا كنت تعرف أي خدعة أو شيء من شأنه تحسين التنفيذ بهذه اللغة ، فيرجى إبلاغي بذلك!ولكن كما في السابق ، نرحب أيضًا بالتعليقات حول استخدام اللغات الأخرى!

شكرًا!وآسف إذا كان السؤال أساسيًا جدًا ، لكني لست على دراية بالأكوام على الإطلاق.هذه هي المرة الأولى التي أواجه فيها مهمة تنفيذ ...

شكرا مرة أخرى!

Answer 1

قد تجد المقالة الثالثة في http://themonadreader.files.wordpress.com / 2010/05 / issue16.pdf ذات صلة.

Answer 2

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

إذا لم تكن على دراية بهياكل البيانات الوظيفية ، أقترح أن تبدأ بـ كتاب أو أطروحة (فصول من الفائدة: 6.2.2 ، 7.2.2 على الأقل).

---

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

PS. هذه الإجابة cstheory.se رائعة

Answer 3

لديهم تعقيد زمني مختلف في عمليات مختلفة في قائمة انتظار الأولوية. هنا جدول مرئي لك Genacodicetagpre

حصلت على هذه الصورة من شرائح محاضرة برينستون

الكومة الثنائية:

---

كومة ذات الحدين:

---

كومة فيبوناتشي:

ملاحظة: تبدو كومة فيبوناتشي ذات الحدين مألوفة لكنهما مختلفتان تمامًا:

• الكومة ذات الحدين: ادمج الأشجار بلهفة بعد كل إدخال.
• كومة فيبوناتشي: تأجيل الدمج ببطء حتى الدقيقة التالية للحذف.

Answer 4

بعض الإشارات إلى الكومة الوظيفية ذات الحدين وكومة فيبوناتشي وكومة الاقتران: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

إذا كان الأداء هو المشكلة حقًا ، أقترح استخدام كومة الاقتران.الخطر الوحيد هو أن الأداء لا يزال تخمينًا حتى الآن.لكن التجارب أظهرت أن الأداء جيد جدًا.