जावा की प्राथमिकता Queue के लिए अंतर्निहित पुनरावर्तक किसी भी विशेष क्रम में डेटा संरचना को पार नहीं करता है। क्यूं कर?

Question

यह सीधे Java Docs से है:

इस वर्ग और उसके इटरेटर संग्रह और इटरेटर इंटरफेस के वैकल्पिक तरीकों के सभी लागू। विधि इटरेटर() में दिए गए इटरेटर को किसी भी विशेष क्रम में प्राथमिकता कतार के तत्वों को पार करने की गारंटी नहीं है। यदि आपको आदेश दिया गया ट्रैवर्सल की आवश्यकता है, तो Arrays.sort (pq.toArray()) का उपयोग करने पर विचार करें।

तो मूल रूप से, मेरे PriorityQueue ठीक काम करता है, लेकिन स्क्रीन का अपना toString में बनाया() विधि का उपयोग करने के लिए इसे बाहर मुद्रण मुझे कार्रवाई में इस विसंगति को देखने के लिए कारण होता है, और अगर किसी को समझा सकता है क्यों यह है कि सोच रहा था प्रदान किया गया इटरेटर (और आंतरिक रूप से उपयोग किया जाता है) प्राथमिकता क्यूई को अपने प्राकृतिक क्रम में पार नहीं करता है?

Answer 1

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

Answer 2

पहले अनुमान पर, यह शायद उस क्रम में डेटा को घुमा रहा है जिसमें यह संग्रहीत है। कतार में किसी आइटम को सम्मिलित करने के लिए समय को कम करने के लिए, यह सामान्य रूप से क्रमबद्ध क्रम में सभी आइटमों को संग्रहीत नहीं करता है।

Answer 3

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

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

Answer 4

बाइनरी ढेर प्राथमिकता कतारों को लागू करने का एक प्रभावी तरीका है। एक ढेर बनाने के आदेश के बारे में एकमात्र गारंटी यह है कि शीर्ष पर आइटम की सर्वोच्च प्राथमिकता है (शायद यह कुछ आदेश के अनुसार "सबसे बड़ा" या "सबसे छोटा" है)। एक ढेर एक बाइनरी पेड़ है जिसमें गुण हैं: आकार की संपत्ति: पेड़ ऊपर से नीचे बाएं से दाएं ऑर्डर प्रिंटर: किसी भी नोड पर तत्व बड़ा होता है (या छोटे से सबसे छोटी प्राथमिकता होने पर छोटा होता है) बच्चों नोड्स। जब पुनरावर्तक सभी तत्वों पर जाता है तो यह शायद स्तर-ऑर्डर ट्रैवर्सल में ऐसा करता है, यानी यह अगले स्तर पर जाने से पहले प्रत्येक स्तर पर प्रत्येक नोड में जाता है। चूंकि ऑर्डर के बारे में एकमात्र गारंटी है कि नोड के अपने बच्चों की तुलना में उच्च प्राथमिकता है, इसलिए प्रत्येक स्तर में नोड्स किसी विशेष क्रम में नहीं होंगे।

Answer 5

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