सॉफ्ट हीप

For the band, see Soft Heap.

कंप्यूटर विज्ञान में, सॉफ्ट हीप सरल हीप (डेटा संरचना) का प्रकार है जिसमें 5 प्रकार के ऑपरेशनों के लिए निरंतर परिशोधित विश्लेषण समय जटिलता होती है। यह ढेर में अधिकतम स्थिर संख्या में मानों की कुंजियों को सावधानीपूर्वक भ्रष्ट (बढ़ाकर) करके प्राप्त किया जाता है।

विवरण

निरंतर समय संचालन हैं:

• create(S): नया सॉफ्ट हीप बनाएं
• सम्मिलित करें (एस, एक्स): तत्व को नरम ढेर में डालें
• मेल्ड(एस, एस'): दो नरम ढेर की सामग्री को में मिलाएं, दोनों को नष्ट कर दें
• डिलीट(एस, एक्स): सॉफ्ट हीप से तत्व हटाएं
• फाइंडमिन(एस): सॉफ्ट हीप में न्यूनतम कुंजी वाला तत्व प्राप्त करें

अन्य ढेर जैसे फाइबोनैचि ढेर बिना किसी भ्रष्टाचार के इनमें से अधिकांश सीमाएँ प्राप्त करते हैं, लेकिन महत्वपूर्ण डिलीट ऑपरेशन पर निरंतर समयबद्धता प्रदान नहीं कर सकते हैं। भ्रष्टाचार की मात्रा को पैरामीटर ε की पसंद से नियंत्रित किया जा सकता है, लेकिन इसे जितना कम सेट किया जाएगा, सम्मिलन के लिए उतना ही अधिक समय की आवश्यकता होगी (ε की त्रुटि दर के लिए बिग-ओ संकेतन (लॉग 1/ε))।

अधिक सटीक रूप से, सॉफ्ट हीप द्वारा दी जाने वाली गारंटी निम्नलिखित है: 0 और 1/2 के बीच निश्चित मान ε के लिए, किसी भी समय अधिकतम ε*n दूषित कुंजियाँ होंगी ढेर, जहां n अब तक डाले गए तत्वों की संख्या है। ध्यान दें कि यह इस बात की गारंटी नहीं देता है कि ढेर में वर्तमान में कुंजियों का केवल निश्चित प्रतिशत ही दूषित है: सम्मिलन और विलोपन के दुर्भाग्यपूर्ण अनुक्रम में, ऐसा हो सकता है कि ढेर में सभी तत्वों में दूषित कुंजियाँ होंगी। इसी तरह, हमें इस बात की कोई गारंटी नहीं है कि फाइंडमिन और डिलीट के साथ ढेर से निकाले गए तत्वों के अनुक्रम में, केवल निश्चित प्रतिशत में दूषित कुंजियाँ होंगी: दुर्भाग्यपूर्ण परिदृश्य में केवल दूषित तत्व ढेर से निकाले जाते हैं .

सॉफ्ट हीप को 2000 में बर्नार्ड चेज़ेल द्वारा डिज़ाइन किया गया था। संरचना में भ्रष्टाचार शब्द उस चीज़ का परिणाम है जिसे चेज़ेल ने सॉफ्ट हीप में कारपूलिंग कहा था। सॉफ्ट हीप में प्रत्येक नोड में कुंजियों की लिंक्ड-सूची और सामान्य कुंजी होती है। सामान्य कुंजी लिंक्ड-सूची में कुंजियों के मानों की ऊपरी सीमा होती है। बार जब कोई कुंजी लिंक्ड-लिस्ट में जोड़ दी जाती है, तो इसे दूषित माना जाता है क्योंकि इसका मूल्य किसी भी सॉफ्ट हीप ऑपरेशन में फिर से प्रासंगिक नहीं होता है: केवल सामान्य कुंजियों की तुलना की जाती है। यही तो मुलायम ढेरों को मुलायम बनाता है; आप निश्चित नहीं हो सकते कि आपके द्वारा इसमें डाला गया कोई विशेष मूल्य दूषित हो जाएगा या नहीं। इन भ्रष्टाचारों का उद्देश्य प्रभावी रूप से डेटा की सूचना एन्ट्रापी को कम करना है, जिससे डेटा संरचना को ढेर के संबंध में सूचना सिद्धांत | सूचना-सैद्धांतिक बाधाओं को तोड़ने में सक्षम बनाया जा सके।

अनुप्रयोग

अपनी सीमाओं और अप्रत्याशित प्रकृति के बावजूद, सॉफ्ट हीप्स नियतात्मक एल्गोरिदम के डिजाइन में उपयोगी हैं। न्यूनतम फैले हुए पेड़ को खोजने के लिए आज तक की सबसे अच्छी जटिलता प्राप्त करने के लिए उनका उपयोग किया गया था। उनका उपयोग आसानी से इष्टतम चयन एल्गोरिदम, साथ ही निकट-सॉर्टिंग एल्गोरिदम बनाने के लिए भी किया जा सकता है, जो एल्गोरिदम हैं जो प्रत्येक तत्व को उसकी अंतिम स्थिति के पास रखते हैं, ऐसी स्थिति जिसमें सम्मिलन सॉर्ट तेज़ होता है।

सबसे सरल उदाहरणों में से चयन एल्गोरिथ्म है। मान लें कि हम n संख्याओं के समूह में से सबसे बड़ा k ज्ञात करना चाहते हैं। सबसे पहले, हम 1/3 की त्रुटि दर चुनते हैं; अर्थात्, हमारे द्वारा डाली गई अधिकतम 33% कुंजियाँ दूषित हो जाएँगी। अब, हम सभी n तत्वों को ढेर में सम्मिलित करते हैं - हम मूल मानों को सही कुंजियाँ कहते हैं, और ढेर में संग्रहीत मानों को संग्रहीत कुंजियाँ कहते हैं। इस बिंदु पर, अधिकांश n/3 कुंजियाँ दूषित हो जाती हैं, अर्थात, अधिक से अधिक n/3 कुंजियाँ संग्रहीत कुंजी सही कुंजी से बड़ी होती हैं, अन्य सभी के लिए संग्रहीत कुंजी सही कुंजी के बराबर होती है।

इसके बाद, हम ढेर से न्यूनतम तत्व को n/3 बार हटाते हैं (यह संग्रहीत कुंजी के अनुसार किया जाता है)। चूँकि अब तक हमारे द्वारा किए गए सम्मिलनों की कुल संख्या अभी भी n है, ढेर में अभी भी अधिकतम n/3 दूषित कुंजियाँ हैं। तदनुसार, ढेर में शेष कुंजियों में से कम से कम 2n/3 − n/3 = n/3 दूषित नहीं हैं।

मान लीजिए कि हमारे द्वारा हटाए गए तत्वों में L सबसे बड़ी सही कुंजी वाला तत्व है। L की संग्रहीत कुंजी संभवतः इसकी सही कुंजी (यदि L दूषित हो गई थी) से बड़ी है, और यहां तक ​​​​कि यह बड़ा मान ढेर में शेष तत्वों की सभी संग्रहीत कुंजियों से छोटा है (क्योंकि हम न्यूनतम हटा रहे थे)। इसलिए, L की सही कुंजी नरम ढेर में शेष n/3 अदूषित तत्वों से छोटी है। इस प्रकार, L तत्वों को 33%/66% और 66%/33% के बीच कहीं विभाजित करता है। फिर हम जल्दी से सुलझाएं से विभाजन एल्गोरिदम का उपयोग करके एल के बारे में सेट को विभाजित करते हैं और उसी एल्गोरिदम को फिर से एल से कम संख्याओं के सेट या एल से अधिक संख्याओं के सेट पर लागू करते हैं, जिनमें से कोई भी 2n/3 तत्वों से अधिक नहीं हो सकता है। चूँकि प्रत्येक सम्मिलन और विलोपन के लिए O(1) परिशोधन समय की आवश्यकता होती है, कुल नियतात्मक समय T(n) = T(2n/3) + O(n) है। मास्टर_प्रमेय (एल्गोरिदम का विश्लेषण)#केस 3 उदाहरण का उपयोग करते हुए मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)|विभाजित और जीत पुनरावृत्ति के लिए मास्टर प्रमेय (ε=1 और c=2/3 के साथ), हम जानते हैं कि T(n) = Θ(एन).

अंतिम एल्गोरिदम इस तरह दिखता है:

'फ़ंक्शन' SoftHeapSelect(a[1..n], k)
 'यदि' k = 1 'तो वापसी' न्यूनतम(a[1..n])
 बनाएँ(एस)
 'के लिए' मैं 'से' 1 'से' एन
 सम्मिलित करें(एस, ए[i])
 'के लिए' मैं 'से' 1 'से' एन/3
 x := फाइंडमिन(एस)
 हटाएं(एस, एक्स)
 xIndex := विभाजन(a, x) // धुरी x का नया सूचकांक लौटाता है
 'अगर' k <xIndex
 SoftHeapSelect(a[1..xIndex-1], k)
 'अन्य'
 SoftHeapSelect(a[xIndex..n], k-xIndex+1)

संदर्भ

• Chazelle, Bernard (November 2000). "The soft heap: an approximate priority queue with optimal error rate" (PDF). J. ACM. 47 (6): 1012–1027. CiteSeerX 10.1.1.5.9705. doi:10.1145/355541.355554. S2CID 12556140.
• Kaplan, Haim; Zwick, Uri (2009). "A simpler implementation and analysis of Chazelle's soft heaps". Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. pp. 477–485. CiteSeerX 10.1.1.215.6250. doi:10.1137/1.9781611973068.53. ISBN 978-0-89871-680-1.