Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> प्रोग्रामिंग

सॉफ्ट हीप (Soft Heaps)


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

  • create(s) - एक नया सॉफ्ट हीप s बनाता है
  • insert(s, y) - एक एलिमेंट y को सॉफ्ट हीप s में इन्सर्ट करता है
  • meld(s, s') - दो सॉफ्ट हीप s और s' को एक में मिलाता है, दोनों को नष्ट करके
  • delete(s, y) - एक एलिमेंट y को सॉफ्ट हीप s से डिलीट करता है
  • findmin(s) - सॉफ्ट हीप s में सबसे कम की वाले एलिमेंट को प्राप्त करता है

फाइबोनैचि हीप जैसे अन्य हीप इनमें से अधिकांश बाउंड्स को बिना किसी करप्शन के प्राप्त करते हैं, लेकिन डिलीट ऑपरेशन पर कॉन्स्टेंट-टाइम बाउंड प्रदान नहीं कर सकते। करप्शन की मात्रा को पैरामीटर ε (0 और 1/2 के बीच) की पसंद द्वारा नियंत्रित किया जा सकता है, लेकिन यह जितना कम सेट किया जाता है, इन्सर्शन में उतना ही अधिक समय लगता है (ε त्रुटि दर के लिए O(log 1/ε))।

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

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

  1. सिमेट्रिक मिन-मैक्स हीप्स (SMMH) सिमेट्रिक मिन-मैक्स हीप्स (SMMH)

    सिमेट्रिक मिन-मैक्स हीप (SMMH) एक **सिमेट्रिक मिन-मैक्स हीप (SMMH)** एक पूर्ण बाइनरी ट्री है जिसमें: **रूट खाली** होता है (कोई तत्व नहीं)। प्रत्येक अन्य नोड में **ठीक एक तत्व** होता है। कुल नोड्स = `m + 1` (जहां `m` तत्वों की संख्या है)। संरचनात्मक गुण किसी भी नोड y के लिए जिसके सबट्री में तत्व

  1. पेयरिंग हीप के प्रकार पेयरिंग हीप के प्रकार

    एक पेयरिंग हीप या तो एक खाली हीप हो सकता है, या एक पेयरिंग ट्री जिसमें एक रूट एलिमेंट और संभावित रूप से खाली पेयरिंग ट्रीज की सूची होती है।हीप ऑर्डरिंग गुण की आवश्यकता है कि किसी भी नोड का पैरेंट नोड स्वयं से अधिक न हो।निम्नलिखित विवरण एक विशुद्ध रूप से फंक्शनल हीप पर विचार करता है जो डिक्रीज़-की ऑप

  1. पेयरिंग हीप पेयरिंग हीप

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