प्राथमिकता कतारों पर सबसे शोध पत्र में, में प्रत्येक तत्व कतार में प्राथमिकता नामक एक संबद्ध संख्या होती है जिसे तत्व डालने पर सेट किया जाता है। तत्वों को प्राथमिकता बढ़ाने के क्रम में हटा दिया जाता है। अधिकांश प्रोग्रामिंग भाषाएं जो प्राथमिकता कतारों का समर्थन करती हैं, वास्तव में स्पष्ट प्राथमिकताओं का उपयोग नहीं करती हैं और इसके बजाय तुलनात्मक रूप से निर्भर करती हैं तत्वों को रैंक करने के लिए फ़ंक्शन, लेकिन मुलायम ढेर "संबंधित संख्यात्मक प्राथमिकता" मॉडल का उपयोग करता है।
Bec प्राथमिकता कतार प्राथमिकता के बढ़ते क्रम में तत्वों को हटाते हैं, उनका उपयोग मूल्यों के अनुक्रम को क्रमबद्ध करने के लिए किया जा सकता है - प्रत्येक तत्व को प्राथमिकता कतार में अनुक्रम में अपनी रैंक के बराबर प्राथमिकता के साथ डालने से शुरू करें, फिर प्राथमिकता कतार से सभी तत्वों को हटाएं । यह तत्व क्रमबद्ध क्रम में बाहर खींचता है।
प्राथमिकता कतारों और सॉर्टिंग के बीच यह कनेक्शन लागत पर आता है, हालांकि। तुलना सॉर्टिंग एल्गोरिदम पर कम सीमाएं ज्ञात हैं (कोई तुलना क्रमबद्ध एल्गोरिदम में रनटाइम हो सकता है जो ओ (एन लॉग एन) से बेहतर है)। नतीजतन, किसी भी तुलना-आधारित प्राथमिकता कतार के रनटाइम पर निचला बाध्य है। विशेष रूप से, एन एनक्यूज और एन डेक्यूज़ की कुल लागत ओ (एन लॉग एन) से बेहतर नहीं होनी चाहिए। ज्यादातर समय, यह ठीक है, लेकिन कुछ मामलों में यह पर्याप्त तेज़ नहीं है।
जब तक प्राथमिकता कतार इनपुट अनुक्रम को सॉर्ट करने के लिए उपयोग किया जा सकता है, एन एनक्यूज़ और एन डेक्यू के रनटाइम कभी भी ओ (एन लॉग एन) को हरा नहीं देगा। लेकिन क्या होगा यदि प्राथमिकता कतार इनपुट को सॉर्ट नहीं करती है? इसे चरम पर ले जाएं - यदि प्राथमिकता कतार पूरी तरह से मनमानी क्रम में तत्वों को वापस रखती है, तो समय में एन एनक्यू और एन डेक्यू लागू करना संभव है ओ (एन) - उदाहरण के लिए, केवल स्टैक या कतार का उपयोग करें।
Intuitively, आप में से "हमेशा अनुसार क्रमबद्ध" और दो चरम सीमाओं के बीच एक पुल के रूप में एक नरम ढेर के बारे में सोच सकता है "जो भी कोई गारंटी आदेश के बारे में।" प्रत्येक प्रकार के ढेर को कुछ मात्रा और ईपीएसलॉन पर पैरामीटर किया जाता है; जिसे "भ्रष्टाचार पैरामीटर" कहा जाता है जो यह निर्धारित करता है कि मुलायम ढेर से निकलने वाले मूल्यों को कैसे क्रमबद्ध किया जा सकता है। विशेष रूप से, के रूप में और epsilon; 0 के करीब आता है, आउटपुट प्रगतिशील रूप से अधिक क्रमबद्ध होगा, और & epsilon के रूप में; 1 के करीब आता है, उत्पादन प्रगतिशील रूप से अधिक मनमाना हो जाएगा। उचित रूप से, मुलायम ढेर परिचालनों का रनटाइम ओ (लॉग और ईपीएसलॉन; -1) के कार्य के रूप में निर्धारित किया जाता है, इसलिए संचालन का रनटाइम सस्ता और सस्ता हो जाता है और ईपीएसलॉन; ऊपर जाता है (और, इसलिए, उत्पादन कम क्रमबद्ध हो जाता है) और संचालन और अधिक महंगा और ईपीएसलॉन मिलता है; नीचे चला जाता है (जिस स्थिति में आउटपुट अधिक से अधिक क्रमबद्ध हो जाता है)।
नरम ढेर ठीक quantifies कैसे अवर्गीकृत उत्पादन की नई अवधारणा का उपयोग करेंगे "भ्रष्टाचार।" एक सामान्य प्राथमिकता कतार में, एक बार जब आप कोई तत्व/प्राथमिकता जोड़ी डालते हैं, तो तत्व की प्राथमिकता कभी भी नहीं बदली जाती है। मुलायम ढेर में, प्राथमिकता से जुड़े तत्व दूषित बन सकते हैं जब तत्व मुलायम ढेर के अंदर होता है। जब किसी तत्व की प्राथमिकता दूषित हो जाती है, तो इसकी प्राथमिकता कुछ राशि से बढ़ जाती है। (चूंकि मुलायम ढेर प्राथमिकता के बढ़ते क्रम में तत्वों को हटा देता है, इसलिए तत्व बढ़ने की प्राथमिकता का मतलब है कि यह कतार से बाहर आने से पहले सामान्य रूप से होना चाहिए)। दूसरे शब्दों में, भ्रष्टाचार तत्वों को क्रमबद्ध क्रम में नहीं आने का कारण बनता है, क्योंकि तत्वों की प्राथमिकताओं को अस्वीकार करते समय जरूरी नहीं है जब वे enqueued हैं।
& epsilon की पसंद; धुनें कि उनकी प्राथमिकताओं में कितने अलग तत्व भ्रष्ट हो सकते हैं। के साथ & epsilon; छोटे, कम तत्वों ने प्राथमिकताओं को दूषित कर दिया है, और साथ ही ईपीएसलॉन; बड़े, अधिक तत्वों को प्राथमिकताओं को दूषित कर दिया जाएगा।
अब
, अपने विशिष्ट सवाल - कैसे तत्वों 'प्राथमिकताओं दूषित, और कैसे आपको लगता है कि मदद करता है? आपका पहला सवाल एक अच्छा है - डेटा संरचना कैसे तय करती है कि प्राथमिकताओं को भ्रष्ट करने के लिए कब? इसे देखने के दो तरीके हैं। सबसे पहले, आप एक डेटा ढांचे के रूप में मुलायम ढेर के बारे में सोच सकते हैं जहां आप पहले से निर्दिष्ट करते हैं कि भ्रष्टाचार कितना स्वीकार्य है (वह है और ईपीएसलॉन; पैरामीटर), और डेटा संरचना तब आंतरिक रूप से निर्णय लेती है जब प्राथमिकताओं को कब और कैसे भ्रष्ट करना है, कुछ भ्रष्टाचार के स्तर से अधिक नहीं है। यदि ऐसा लगता है कि डेटा संरचना के लिए अजीब लगता है तो इस तरह के फैसले करें, ब्लूम फ़िल्टर या स्कीप्लिस्ट जैसे कुछ के बारे में सोचें, जहां वास्तव में आंतरिक रूप से यादृच्छिक विकल्प चल रहे हैं जो डेटा संरचना के अवलोकन योग्य व्यवहार को प्रभावित कर सकते हैं। यह पता चला है कि मुलायम ढेर आम तौर पर यादृच्छिकता (एक प्रभावशाली विशेषता है!) का उपयोग करके लागू नहीं किया जाता है, लेकिन यह विशेष रूप से यहां प्रासंगिक नहीं है।
आंतरिक रूप से, नरम ढेर के दो ज्ञात कार्यान्वयन (Chazelle के मूल कागज से एक है, और एक बाद की सफाई द्विआधारी पेड़ का उपयोग कर) एक तकनीक है जहां तत्वों साथ रखे जाते हैं और सभी शेयर एक आम प्राथमिकता carpooling कहा जाता है का उपयोग कर भ्रष्टाचार को लागू। भ्रष्टाचार होता है क्योंकि प्रत्येक समूह में सभी तत्वों की मूल प्राथमिकताओं को भुला दिया जाता है और इसके बजाय एक नई प्राथमिकता का उपयोग किया जाता है। तत्वों को समूहीकृत करने के बारे में वास्तविक विवरण भयभीत रूप से जटिल है और वास्तव में यह देखने लायक नहीं है, इसलिए शायद इसे छोड़ना सबसे अच्छा है क्योंकि "डेटा संरचना दूषित होने का विकल्प चुनती है, हालांकि यह चाहती है, जब तक यह अधिक तत्वों को दूषित न करे जब आपने उठाया और ईपीएसलॉन निर्दिष्ट किया था; "
अगला, यह उपयोगी क्यों है? अभ्यास में, यह नहीं है। मुलायम ढेर लगभग सैद्धांतिक हित में है। सिद्धांत में यह अच्छा कारण यह है कि नरम ढेर से एन सम्मिलन और एन हटाने का रनटाइम ओ (एन) हो सकता है - ओ (एन लॉग एन) से तेज़ - यदि & epsilon; सही ढंग से चुना जाता है। मूल रूप से, मुलायम ढेर को कम से कम पेड़ के निर्माण के लिए एक तेज एल्गोरिदम में एक बिल्डिंग ब्लॉक के रूप में उपयोग किया जाता था। इन्हें रैखिक-समय चयन के लिए एक नए एल्गोरिदम में भी उपयोग किया जाता है, प्रसिद्ध मध्य-मध्य-चिकित्सा एल्गोरिदम के बाद से रैखिक समय में चलाने के लिए ऐसा पहला निर्धारक एल्गोरिदम।इन दोनों मामलों में, नरम ढेर का उपयोग इनपुट तत्वों को इस तरह से क्रमबद्ध करने के लिए किया जाता है जिससे एल्गोरिदम को सॉर्ट किए गए अनुक्रम का अनुमान लगाया जा सके, जिस बिंदु पर एल्गोरिदम कुछ अतिरिक्त तर्क को कम करने के लिए सही करता है पूर्णता। आप निश्चित रूप से अभ्यास में इस्तेमाल होने वाले नरम ढेर को कभी नहीं देख पाएंगे, लेकिन यदि आप एक ऐसा मामला ढूंढते हैं जहां आप करते हैं, तो कृपया एक टिप्पणी छोड़ दें और मुझे बताएं!
संक्षेप में:
- भ्रष्ट प्राथमिकताओं सही छंटाई (सटीक है, लेकिन धीमी गति से) और मनमाने ढंग से आदेश (अयथार्थ, लेकिन बहुत तेजी से) के बीच एक समंजन करने का एक तरीका है। पैरामीटर और ईपीएसलॉन; निर्धारित करता है कि स्पेक्ट्रम पर भ्रष्टाचार की मात्रा कहां है।
- भ्रष्टाचार नरम ढेर में मौजूदा तत्वों की प्राथमिकताओं को बदलकर काम करता है, विशेष रूप से कुछ तत्वों की प्राथमिकताओं को बढ़ाकर। कम भ्रष्टाचार लगभग क्रमबद्ध अनुक्रमों से मेल खाता है, जबकि उच्च भ्रष्टाचार अधिक मनमाना अनुक्रमों से मेल खाता है।
- जिस तरह भ्रष्टाचार किया जाता है वह डेटा-संरचना विशिष्ट और समझने में बहुत मुश्किल है। जब उन्हें आवश्यकता होती है तो भ्रष्टाचार करने के रूप में मुलायम ढेर के बारे में सोचना सबसे अच्छा होता है, लेकिन कभी भी ऐसा नहीं होता है जो ईपीएसलॉन की पसंद से लगाई गई सीमा से अधिक हो।
- भ्रष्टाचार सैद्धांतिक सेटिंग्स में सहायक है जहां सॉर्टिंग बहुत धीमी है, लेकिन व्यावहारिक उद्देश्यों के लिए लगभग सही ढंग से सॉर्ट किया गया अनुक्रम पर्याप्त है। अभ्यास में उपयोगी होने की संभावना नहीं है।
आशा है कि इससे मदद मिलती है!
तो अज्ञात राशि से किसी भी ऑपरेशन के दौरान मौके के साथ यादृच्छिक रूप से कुंजी की कीमत बढ़ जाती है? इसके अलावा, यह संचालन को तेजी से कैसे बनाता है? मैं क्षमा चाहता हूं अगर यह आपके लिए स्पष्ट है, लेकिन मैं वास्तव में संघर्ष कर रहा हूं। – kalibra