सॉफ्ट हीप

For बैंड, see सॉफ्ट हीप.

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

विवरण

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

• क्रिएट(S): नया सॉफ्ट हीप बनाएं
• इन्सर्ट (s, x): तत्व को नरम हीप में डालें
• मेल्ड(s, s'): दो नरम हीप की कंटेंट को मिलाएं, दोनों को नष्ट कर दें
• डिलीट(s, x): सॉफ्ट हीप से तत्व हटाएं
• फाइंडमिन(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) = Θ(n) का उपयोग किया जाता है

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

function softHeapSelect(a[1..n], k)
    if k = 1 then return minimum(a[1..n])
    create(S)
    for i from 1 to n
        insert(S, a[i])
    for i from 1 to n/3
        x := findmin(S)
        delete(S, x)
    xIndex := partition(a, x)  // Returns new index of pivot x
    if k < xIndex
        softHeapSelect(a[1..xIndex-1], k)
    else
        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.