जावा में प्राथमिकता कतार कक्षा पर remove() फ़ंक्शन के लिए जटिलता (बड़ी-ओएच) क्या है? मुझे कहीं भी दस्तावेज नहीं मिला है, मुझे लगता है कि यह ओ (एन) है, इस पर विचार करते हुए कि आपको इसे हटाने से पहले तत्व ढूंढना है और फिर पेड़ को फिर से बदलना है। लेकिन मैंने दूसरों को देखा है जो असहमत हैं और सोचते हैं कि यह ओ (लॉगन) है। कोई विचार?प्राथमिकता कतार जटिलता समय हटाएं
निकालने के लिए जटिलता हे (एन) के बाद से जटिलता के लिए होता है हे (एन) (जावा की प्राथमिकता कतार कक्षा में)
एक तरीका है यह किया जा सकता है ओ (logn) में अपनी खुद की प्राथमिकता कतार कार्यान्वयन एक सहायक डेटा संरचना को बनाए रखने के लिए हैशैप जैसे कि कतार में अपनी स्थिति के लिए प्राथमिकता कतार में किसी मान से मैपिंग को बनाए रखता है। तो, किसी भी समय - आप किसी भी मूल्य की सूचकांक स्थिति को जानेंगे।
ध्यान दें कि यह संशोधन किसी भी मौजूदा परिचालन के चलने वाले समय को प्रभावित नहीं करता है - आपको केवल ढेर परिचालन के दौरान मैपिंग अपडेट करने की आवश्यकता होगी।
इसलिए यदि मैं किसी तत्व की अनुक्रमणिका स्थिति जानता हूं, तो मैं इसे इंडेक्स के आधार पर प्राथमिकता कतार API में कैसे हटा सकता हूं? (ओ (लॉगएन) समय में) – novalain
@ दुर्भाग्यवश, जावा एपीआई इंडेक्स द्वारा प्राथमिकता कतार में तत्वों तक पहुंचने का एक तरीका नहीं दिखाता है, इसलिए आपको प्राथमिकता कतार के अपने घर-निर्मित कार्यान्वयन का उपयोग करना होगा। –
ओ (लॉग) को अपने स्वयं के कार्यान्वयन से हटाने के लिए कैसे आते हैं और ओ (1) नहीं? मुझे यकीन है कि मुझे कुछ विवरण याद आ रहा है, लेकिन प्राथमिकता कतार केवल एक डेटा संरचना है जो उच्च से कम प्राथमिकता से क्रमबद्ध है। यदि यह एक लिंक्ड सूची का उपयोग करके कार्यान्वित किया गया है, और हम इंडेक्स को जानते हैं, तो क्या हम उस तत्व को हटा नहीं सकते हैं और पिछले नोड को निम्नलिखित नोड से कनेक्ट कर सकते हैं? – user3125693
ओरेकल प्रलेखन के अनुसार: "कार्यान्वयन ध्यान दें:; रेखीय के लिए समय इस कार्यान्वयन हे (लॉग (एन)) enqueing और dequeing विधियों (प्रस्ताव, सर्वेक्षण, निकालें() और जोड़ने) के लिए समय प्रदान करता है निकालें (ऑब्जेक्ट) और इसमें (ऑब्जेक्ट) विधियां हैं और पुनर्प्राप्ति विधियों (चरम, तत्व, और आकार) के लिए निरंतर समय। "
मुझे लगता है कि उसका मतलब है कि निकालें (ऑब्जेक्ट) हटा नहीं है() पहला ओ (एन) है, बाद वाला ओ (लॉग एन) –
'निकालें()' और 'पोल() 'गायब तत्व सेमेन्टिक्स को छोड़कर समान है। एक विशिष्ट आइटम को हटाने ('निकालें (ऑब्जेक्ट)') 'ओ (एन) 'है। मुझे लगता है कि सवाल स्पष्ट नहीं था और यह भी एक वैध जवाब है ... – TWiStErRob
भ्रम वास्तव में अपने "निकालें" समारोह के कारण होता है। जावा में, दो हटाने के कार्य हैं।
हटाएं() -> यह सिर/रूट को हटाने के लिए है, यह ओ (लॉगएन) समय लेता है।
हटाएं (ऑब्जेक्ट ओ) -> यह एक मनमानी वस्तु को हटाने के लिए है। इस ऑब्जेक्ट को ढूंढना ओ (एन) समय लेता है, और इसे हटाने से ओ (लॉगएन) समय लगता है।
क्या आपने जावाडोक पढ़ने पर विचार किया था? ["यह कार्यान्वयन एन (लॉग (एन)) प्रदान करता है जो एनकिंग और डेकिंग विधियों (ऑफ़र, पोल, हटाएं() और एड) के लिए समय प्रदान करता है"] (http://docs.oracle.com/javase/6/docs/api /java/util/PriorityQueue.html)। – EJP
हाँ, मैंने किया। अगली पंक्ति पर यह कहते हैं कि निकालने के लिए रैखिक समय (ऑब्जेक्ट) और इसमें (ऑब्जेक्ट) विधियां हैं; और पुनर्प्राप्ति विधियों (चोटी, तत्व, और आकार) 'के लिए निरंतर समय, जहां मैं उलझन में था। मुझे लगता है कि मुझे अब मिल गया है। – samturner