जावा PriorityQueue अपडेट कर रहा है जब उसके तत्वों प्राथमिकता

Question

बदलने मैं एक Comparator का उपयोग कर वस्तुओं ऑर्डर करने के लिए एक PriorityQueue उपयोग करने के लिए कोशिश कर रहा हूँ।

यह आसानी से प्राप्त किया जा सकता है, लेकिन वस्तुओं वर्ग चर (जिसके साथ तुलनित्र प्राथमिकता की गणना करता है) प्रारंभिक प्रविष्टि के बाद बदल सकते हैं। अधिकांश लोगों ने ऑब्जेक्ट को हटाने, मूल्यों को अपडेट करने और फिर से पुन: सम्मिलित करने का सरल समाधान सुझाया है, क्योंकि यह तब होता है जब प्राथमिकता कतार के तुलनित्र को क्रियान्वित किया जाता है।

क्या ऐसा करने के लिए प्राथमिकता के आसपास एक रैपर वर्ग बनाने के अलावा कोई बेहतर तरीका है?

Answer 1

आप, के रूप में कतार उचित स्थिति में नए तत्व डालने जब वे डाला जाता है से काम करता है को हटाने और फिर से डालने के लिए है। हर बार जब आप कतार से बाहर निकलते हैं तो उच्चतम प्राथमिकता तत्व खोजने के विकल्प से यह बहुत तेज़ है। दोष यह है कि तत्व डालने के बाद आप प्राथमिकता नहीं बदल सकते हैं। एक ट्रीमैप में एक ही सीमा होती है (जैसा कि हैश मैप करता है, जो तब भी टूट जाता है जब उसके तत्वों का हैशकोड सम्मिलन के बाद बदल जाता है)।

यदि आप एक रैपर लिखना चाहते हैं, तो आप तुलना कोड को एनक्यू से डेक्यू में ले जा सकते हैं। आपको अब एनक्यू समय पर सॉर्ट करने की आवश्यकता नहीं होगी (क्योंकि यदि आप परिवर्तन की अनुमति देते हैं तो वैसे भी ऑर्डर विश्वसनीय नहीं होगा)।

लेकिन यह भी बदतर प्रदर्शन करेंगे, और यदि आप प्राथमिकताओं में से किसी को बदलना कतार पर सिंक्रनाइज़ करने के लिए चाहते हैं। चूंकि आपको प्राथमिकताओं को अपडेट करते समय सिंक्रनाइज़ेशन कोड जोड़ने की आवश्यकता है, इसलिए आप केवल डेक्यू और एनक्यू्यू (आपको दोनों मामलों में कतार के संदर्भ की आवश्यकता हो सकती है)।

Answer 2

मुझे नहीं पता कि जावा कार्यान्वयन है या नहीं, लेकिन यदि आप बहुत महत्वपूर्ण मूल्य बदल रहे हैं, तो आप एक फिबोनासी ढेर का उपयोग कर सकते हैं, जिसमें ओ (1) अमूर्त लागत कम हो जाती है एक सामान्य ढेर के रूप में ओ (लॉग (एन)) के बजाय ढेर में प्रवेश।

Answer 3

यह पर सीधे नियंत्रण करता है कि मान बदलते हैं या नहीं।

यदि आप जानते हैं जब मान बदलते हैं, तो आप या तो हटा दें और पुन: लगाएं कर सकते हैं (जो वास्तव में काफी महंगा है, को हटाने के रूप में ढेर के ऊपर एक रेखीय स्कैन की आवश्यकता है!)। इसके अलावा, आप इस स्थिति के लिए एक अद्यतन करने योग्य हेप संरचना (हालांकि स्टॉक जावा में नहीं) का उपयोग कर सकते हैं। अनिवार्य रूप से, यह एक ढेर है जो हैशपैप में तत्वों की स्थिति को ट्रैक करता है। इस तरह, जब तत्व की प्राथमिकता बदलती है, तो यह ढेर की मरम्मत कर सकती है। तीसरा, आप एक फाइबोनैकी ढेर की तलाश कर सकते हैं जो वही करता है।

अपने अद्यतन दर के आधार पर, एक रेखीय स्कैन/quicksort/QuickSelect हर बार भी काम कर सकते हैं। विशेष रूप से यदि आपके पास pull से अधिक अपडेट हैं, तो यह जाने का तरीका है। यदि आपके पास अद्यतन के बैच हैं और फिर पुल ऑपरेशन के बैच हैं तो QuickSelect शायद सबसे अच्छा है।