जब remove विधि जावा में PriorityQueue ऑब्जेक्ट पर कॉल की जाती है, तो ढेर का सिर हटा दिया जाता है। सिर पर नया न्यूनतम तत्व डालने के लिए, बाकी ढेर पर कोई सॉर्टिंग ऑपरेशन किया जाता है? उदाहरण के लिए, compareTo विधि है जिसे remove कहा जाता है?क्या प्राथमिकता क्यूई की निकासी विधि ढेर को पुनर्व्यवस्थित करती है?
क्षमा करें यदि यह दस्तावेज़ों में है, तो मैं इसे कहीं भी नहीं ढूंढ सकता। अग्रिम में धन्यवाद।
PriorityQueue एक सरणी के रूप में लागू एक संतुलित बाइनरी ढेर के रूप में लागू किया गया है। जब कोई तत्व हटा दिया जाता है, तो ढेर को ढेर के क्रम को रखने के लिए खुद को पुन: व्यवस्थित करना होता है।
सबूत टिप्पणी
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
private transient Object[] queue;
इसके अलावा में है
कार्यान्वयन ध्यान दें: इस कार्यान्वयन enqueing और dequeing तरीकों के लिए हे (लॉग (एन)) समय प्रदान करता है (प्रस्ताव, मतदान, हटाएं() और जोड़ें); निकालने के लिए रैखिक समय (ऑब्जेक्ट) और इसमें (ऑब्जेक्ट) विधियां हैं; और पुनर्प्राप्ति विधियों (चरम, तत्व, और आकार) के लिए निरंतर समय।
remove() के लिए, उदाहरण के लिए, आप हीप की जड़ को हटा देते हैं। आप अंतिम तत्व लेते हैं, यानी। द्विआधारी पेड़ के अंतिम स्तर पर दाएं सबसे अधिक पत्ते, और इसे रूट के रूप में रखें और इसे तब तक खाली कर दें जब तक कि यह इसकी जगह न पाएं (Comparator पर आधारित)। यह सबसे खराब O(log n) समय लेता है।
जबकि मैं मानता हूं कि यह * आवश्यकता * है, क्या दस्तावेज में कुछ भी है जो यह औचित्य देता है कि यह वास्तव में * होता है? – templatetypedef
@templatetypedef जब यह कहता है कि इसे एक हीप के रूप में लागू किया गया है, तो पुनरावृत्ति की आवश्यकता होती है। अन्यथा, यह एक ढेर नहीं है। आप कार्यान्वयन विवरण के लिए शेष स्रोत कोड के माध्यम से जा सकते हैं। –
@templatetypedef, http://goo.gl/cCKOt3 'निकालें (ऑब्जेक्ट ओ)' के लिए स्रोत कोड है, जो वास्तव में 'indexOf (o)' और 'removeAt (i)' कहता है, जहां पूर्व ओ (एन) खोज, और बाद वाला ओ (लॉग (एन)) शिफ्ट ऑपरेशन। – lcn
यह निर्भर करता है। यदि आप हैं जो सरणी में अंतिम तत्व है जो PriorityQueue का समर्थन करता है, तो कोई सहारा नहीं किया जाएगा। आप remove किसी अन्य तत्व है, यह उसके तत्वों (siftUp और siftDown) को पुन: व्यवस्थित करेंगे:
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
private E removeAt(int i) {
assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
मैं सिर्फ प्रलेखन की जाँच की और इस बारे में कुछ भी निर्दिष्ट नहीं था। मैं जवाब सुनने के लिए उत्सुक हूँ! – templatetypedef
धन्यवाद, जानकर खुशी हुई कि मुझे कुछ भी याद नहीं आ रहा है! – chm