तत्वों को अद्यतन करने के बाद java.util.PriorityQueue को रीहाइपी करें

Question

मेरे पास प्राथमिकता क्यूई है जिसमें कुछ ऑब्जेक्ट्स हैं। जब मैं प्रारंभ में प्राथमिकता कतार में तत्वों को सम्मिलित करता हूं तो ऑर्डरिंग डेटा संरचना द्वारा बनाए रखा जाता है। अब एक निष्कासन ऑपरेशन के बाद मैं कुछ संदर्भों को अद्यतन करता हूं जो प्राथमिकता कतार द्वारा आयोजित किए जा रहे हैं। आदर्श रूप से इसे प्राथमिकता कतार पर एक पुनर्मूल्यांकन ऑपरेशन की आवश्यकता होती है, लेकिन जैसा कि स्पष्ट है क्योंकि मैं चयनित संदर्भों को संशोधित कर रहा हूं, बाहरी रूप से एक पुनरावृत्ति को ट्रिगर नहीं किया जा सकता है। तो यह सुनिश्चित करने का सबसे अच्छा तरीका क्या है कि मैं कतार के अंदर मनमानी तत्वों में संशोधन की उपस्थिति में तेजी से निकालने जैसे अधिकतम ढेर का लाभ प्राप्त करने में सक्षम हूं? मुझे लगता है कि मुझे बेहतर डेटा संरचना चाहिए?

अधिक विशिष्ट होने के लिए मुझे जावा में फाइबोनैकी ढेर जैसे कुछ के कार्यान्वयन की आवश्यकता है। http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm क्या यह उपलब्ध है?

Answer 1

आप अपने पेड़ का उपयोग कर सकते हैं जो ढेर के बजाय डुप्लिकेट तत्वों को अनुमति देता है। आसान हालांकि, आप TreeMap<PriorityKey, LinkedHashSet<Value>> का उपयोग कर सकते हैं। सभी आपरेशनों हे (लॉग priorityType) कर रहे हैं:

• जोड़ने, get(priority).add(value) है रिटर्न अशक्त मिलता है, put(priority, new LinkedHashSet())
• , को हटाने के लिए एक मनमाना तत्व इसी तरह की है की जरूरत को छोड़कर नक्शे से बाहर प्राथमिकता दूर करने के लिए करता है, तो सेट है खाली।

  Entry<PriorityKey, LinkedHashSet<Value>> e = map.firstEntry(); 
  if (e==null) return null; 
  Iterator<Value> i = e.getValue().iterator(); 
  Value v = i.next(); //must always have at least one element. 
  i.remove(); 
  if (!i.hasNext()) map.remove(e.getKey()); 
  return v; 
  

  फिर भी यदि आप प्राथमिकता आप को हटाने और तत्व जोड़ने के लिए बदलने की जरूरत है -

• चुनाव()

है।

Answer 2

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

http://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html

ट्री-मैप लागू करता NavigableMap, और इसलिए प्रदान करता है firstEntry/lastEntry विधियों, और कई और।