قائمة انتظار أولوية جافا

Question

جافا طابور الأولوية هو بنية البيانات مع O(log n) التعقيد لوضع (الإدراج) و O(log n) للاستطلاع (استرجاع وإزالة العنصر الأدنى).

C++ STL multimap لديه نفس الوظيفة ولكن O(1) تعقيد استرجاع وإزالة العنصر الأدنى (البدء والمسح).هل هناك ما يعادلها في جافا؟

Answer 1

مجموعات جوجل يوفر تنفيذ Multimap. على وجه التحديد، يمكن للTreeMultimap استخدام المقارنة لفرز على أساس إما مفاتيح أو قيم أو كليهما.

Answer 2

جرب ال مجموعات أباتشي كومنز.

يقوم MultiHashMap وMultiValueMap (المرتبطان بهذه الصفحة) بتنفيذ الواجهة فعليًا.

هناك في الواقع أ طابور الأولوية هناك أيضًا، ولكن تم تخفيض قيمتها لصالح حزمة العازلة.

Answer 3

أولاً، أتحقق من أن الخريطة المتعددة لـ C++ تعطي O(1) لـ إزالة العنصر الحد الأدنىالهياكل الأكثر شيوعًا للخرائط المنسقة/قوائم الانتظار ذات الأولوية هي الهياكل الشجرية التي الاستعلام يحتوي العنصر min على تعقيد O(1)، ولكن إزالة إنه O(سجل ن).

ومع ذلك، أعتقد أن قائمة التخطي (كما تم تنفيذها بواسطة Java ConcurrentSkipListMap) قد أعطيك O(1) لإزالة الحد الأدنى من العناصر، لكنني لست متأكدًا تمامًا.إحدى المشكلات عند تقييم أداء ConcurrentSkipListMap هي أن عمليات الاجتياز تعمل على "ترتيب" العلامات التي خلفتها عمليات الحذف السابقة.لذا فإن تعقيد العملية يمكن أن يعتمد في الواقع على طبيعة العمليات السابقة.(من ناحية أخرى، على مستوى ما، ينطبق هذا إلى حد كبير على أي خوارزمية:ما إذا كانت بعض البيانات موجودة في ذاكرة التخزين المؤقت لوحدة المعالجة المركزية يمكن أن تعتمد على ما إذا كانت عملية سابقة قد وضعتها هناك ...)

ملاحظة.نسيت أن أقول:ينظر الى ConcurrentSkipListMap.pollFirstEntry().

Answer 4

وstd:multimap سيكون هيكل شجرة، وهو ما يعني أن إضافة وإزالة معا سيكون O (سجل ن).