كيف يمكنني تتبع أصغر عنصر في المجموعة بكفاءة؟

Question

في سياق أسئلة البرمجة:لنفترض أن هناك مجموعة من الكائنات التي يمكن مقارنتها ببعضها البعض وفرزها.ما هي الطريقة الأكثر فعالية لتتبع أصغر عنصر في المجموعة عند إضافة الكائنات وإزالة أصغر العناصر الحالية أحيانًا؟

Answer 1

يعد استخدام min-heap هو أفضل طريقة.

http://en.wikipedia.org/wiki/Heap_(data_structure)

وهي مصممة خصيصا لهذا التطبيق.

Answer 2

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

Answer 3

@هاربريت
هذا ليس الأمثل.عندما تتم إزالة كائن ما، سيتعين على إريكسون مسح المجموعة بأكملها للعثور على الأصغر الجديد.

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

Answer 4

لعمليات الإزالة العرضية أ كومة فيبوناتشي بل هو أسرع من الكومة الصغيرة.الإدراج هو O(1)، وإيجاد الدقيقة هو أيضًا O(1).الإزالة هي O(log(n))

Answer 5

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

نعم، ولكنك ستحتاج إلى إعادة الفرز في كل إدراج و(ربما) كل عملية حذف، والتي، كما ذكرت، هي O(log(n)).

مع الحل الذي اقترحه Harpreet:

• لديك تمريرة O(n) واحدة في البداية للعثور على أصغر عنصر
• الإدخالات هي O(1) بعد ذلك (يلزم إجراء مقارنة واحدة فقط مع أصغر عنصر معروف بالفعل)
• ستكون عمليات الحذف هي O(n) لأنك ستحتاج إلى إعادة العثور على أصغر عنصر (ضع في اعتبارك أن تدوين Big O هو أسوأ الحالات).يمكنك أيضًا التحسين عن طريق التحقق لمعرفة ما إذا كان العنصر المراد حذفه هو الأصغر (المعروف)، وإذا لم يكن الأمر كذلك، فلا تقم بأي من عمليات إعادة التحقق للعثور على أصغر عنصر.

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

Answer 6

هاربريت:

ستكون الإدخالات في ذلك خطية نظرًا لأنه يتعين عليك نقل العناصر للإدراج.

ألا يعتمد ذلك على تنفيذ المجموعة؟إذا كانت تعمل كقائمة مرتبطة، فستكون الإدخالات O(1)، بينما إذا تم تنفيذها كصفيف فستكون خطية، كما ذكرت.

Answer 7

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

ومع ذلك، إذا كنت تحتاج فقط إلى الدفع/البوب ​​من الأمام/الخلف، فيمكنك فقط استخدام العقل الذي يحقق وقتًا ثابتًا مستهلكًا لجميع العمليات (بما في ذلك findmin).يمكنك ان تفعل بحث على موقع Scholar.google.com لمعرفة المزيد عن هذا الهيكل.لقد تعاونت أنا وصديق مؤخرًا للوصول إلى نسخة أسهل بكثير في الفهم والتنفيذ من العقل أيضًا.إذا كان هذا هو ما تبحث عنه فيمكنني نشر التفاصيل لك.