डी-एरी हीप: Difference between revisions

Revision as of 01:19, 4 August 2023

$d$ -एरी हीप या $d$ -हीप एक प्राथमिक डेटा संरचना होती है, जो बाइनरी हीप का एक सामान्यीकरण होता है जिसमें नोड्स मे 2 के अतिरिक्त $d$ चिल्ड्रेन होते है।^[1]^[2]^[3] इस प्रकार, एक बाइनरी हीप मे 2-हीप और एक टर्नरी हीप मे 3-हीप होते है। टारजन ^[2]और जेन्सेन एट अल के अनुसार,^[4] $d$ -एरी हीप्स का आविष्कार डोनाल्ड बी. जॉनसन ने 1975 में किया था।^[1]

यह डेटा संरचना धीमी प्राथमिकता वाले संक्रिया बहुकार्य को बाइनरी हीप्स की तुलना में अधिक तेज़ी से निष्पादित करने की अनुमति देती है, धीमी गति की कीमत पर न्यूनतम संचालन हटाएं जाते है। यह ट्रेडऑफ़ दिज्क्स्ट्रा के एल्गोरिदम के लिए अच्छा चलन समय की ओर ले जाता है, जिसमें प्राथमिकता वाले संक्रिया बहुकार्य डिलीट मिन संक्रिया बहुकार्य की तुलना में अधिक सामान्य होते है।^[1]^[5] इसके अतिरिक्त, $d$ -एरी हीप्स में बाइनरी हीप्स की तुलना में अच्छा मेमोरी कैश व्यवहार होता है, जो उन्हें सैद्धांतिक रूप से बड़े कठिन स्थिति वाले रनिंग टाइम के अतिरिक्त व्यवहार में अधिक तेजी लाने की अनुमति देता है।^[6] बाइनरी हीप की तरह, $d$ -एरी हीप्स एक इन-प्लेस डेटा संरचना होती है जो हीप की श्रृंखलाओं को संग्रहीत करने के लिए आवश्यक अतिरिक्त स्टॉरिज का उपयोग नहीं करती है। ^[2]^[7]

डेटा संरचना

$d$ -एरी हीप में $n$ वस्तु की एक श्रृंखला होती है,जिनमें से प्रत्येक के साथ एक प्राथमिकता जुड़ी होती है। इन वस्तुओं को संपूर्ण $d$ -एरी ट्री, में नोड्स के रूप में देखा जा सकता है, जो चौड़ाई के पहले ट्रैवर्सल क्रम में सूचीबद्ध हैं: सरणी की स्थिति 0 पर वस्तुओं (शून्य-आधारित नंबरिंग का उपयोग करके) ट्री की जड़ बनाता है, स्थिति 1 से लेकर $d$ तक इसके चाइल्ड नोड होते है इस प्रकार, स्थिति $i$ (किसी भी $i > 0$ के लिए) पर वस्तुओं का मूल तत्व स्थिति $⌊ (i - 1)/ d ⌋$ और उसके चाइल्ड पदों पर $di + 1$ द्वारा $di + d$ स्थिति पर वस्तु होती हैं। बाइनरी हीप के अनुसार, मिन-हीप में, प्रत्येक पद की एक प्राथमिकता होती है जो कम से कम उसके मूल के बराबर बड़ी होती है, अधिकतम-हीप में, प्रत्येक वस्तुओ की एक प्राथमिकता होती है जो उसके मूल से बड़ी नहीं होती है।^[2]^[3]

न्यूनतम-हीप में न्यूनतम प्राथमिकता वाले पद (या अधिकतम-हीप में अधिकतम प्राथमिकता वाले पद) हमेशा सरणी के स्थान 0 पर प्राप्त किया जा सकता है। इस पद को प्राथमिकता से हटाने के लिए, सरणी में अंतिम पद x को उसके स्थान पर ले जाया जाता है, और सरणी की लंबाई को एक से कम कर दी जाती है। फिर, जबकि पद x और उसके चाइल्ड हीप होते है, पद x को उसके चाइल्ड हीप में से एक के साथ बदल दिया जाता है (मिन-हीप में सबसे छोटी प्राथमिकता होती है, या अधिकतम-हीप में सबसे बड़ी प्राथमिकता होती है) , इसे ट्री में और बाद में सरणी में नीचे की ओर ले जाते है। उसी डाउनवर्ड स्वैपिंग प्रक्रिया का उपयोग न्यूनतम-हीप में पद की प्राथमिकता को बढ़ाने के लिए, या अधिकतम-हीप में किसी पद की प्राथमिकता को कम करने के लिए किया जा सकता है।^[2]^[3]

हीप में एक नया पद डालने के लिए, पद को सरणी के अंत में जोड़ा जाता है, और फिर जब हीप का उल्लंघन होता है तो इसे अपने मूल के साथ बदल दिया जाता है, इसे ट्री में ऊपर की ओर और सरणी में पहले ले जाया जाता है उसी अपवर्ड-स्वैपिंग प्रक्रिया का उपयोग न्यूनतम-हीप में किसी पद की प्राथमिकता को कम करने, या अधिकतम-हीप में किसी पद की प्राथमिकता को बढ़ाने के लिए किया जा सकता है।^[2]^[3]

किसी सारणी से एक नया हीप बनाने के लिए $n$ , पद की स्थिति से प्रारंभ करते हुए, रिवर्स ऑर्डर में पद पर लूप कर सकता है $n - 1$ और पद को स्थिति 0 पर समाप्त करते हुए, प्रत्येक पद के लिए डाउनवर्ड-स्वैपिंग प्रक्रिया को प्रारंभ करता है।^[2]^[3]

विश्लेषण

एक $d$ -एरी हीप के साथ $n$ पद, ऊपर की ओर-स्वैपिंग प्रक्रिया और नीचे की ओर-स्वैपिंग प्रक्रिया दोनों ही कार्य कर सकते है $log d n = log n / log d$ । अपवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप में किसी पद की उसके मूल के साथ एकल तुलना सम्मलित होती है, और इसमें निरंतर समय लगता है। इसलिए, हीप में एक नया विषय डालने, न्यूनतम-हीप में किसी पद की प्राथमिकता को कम करने, या अधिकतम-हीप में किसी पद की प्राथमिकता बढ़ाने का समय है $O(log n / log d)$ . डाउनवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप सम्मलित होते है $d$ और $O(d)$ समय लगता है $d - 1$ चाइल्ड की न्यूनतम या अधिकतम संख्या निर्धारित करने के लिए चाइल्ड नोड के विरुद्ध अदला-बदली की आवश्यकता होती है। इसलिए, रूट पद को हटाने, न्यूनतम-हीप में किसी पद की प्राथमिकता बढ़ाने या अधिकतम-हीप में किसी पद की प्राथमिकता कम करने का समय है $O(d log n / log d)$ ^[2]^[3]

$d$ -एन पदोंं के एक सममुच्च हीप, अधिकांश पद ऐसी स्थिति में होता है, जो अंततः ट्री को प्राप्त करता है $d$ -एरी ट्री, और उन वस्तुओ के लिए कोई नीचे की ओर स्वैपिंग नहीं की जाती है। अधिक से अधिक $n / d + 1$ पद गैर-ट्री होते है, और इन्हें कम से कम एक बार नीचे की ओर बदला जा सकता है $O(d)$ उनकी अदला-बदली के लिए चाइल्ड को प्राप्त किया जाता है। अधिक से अधिक $n / d 2 + 1$ नोड्स को दो बार नीचे की ओर स्वैप किया जा सकता है, जिससे अतिरिक्त समय होता है $O(d)$ दूसरे स्वैप के पहले से ही गणना का समय अधिक होता है। इसलिए, इस तरह से हीप बनाने में लगने वाला कुल समय होता है।

\sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).

^[2]^[3]

उपरोक्त का त्रुटिहीन मान ( $d$ -एरी हीप के निर्माण के समय तुलना की सबसे कठिन स्थिति वाली संख्या) को इसके बराबर माना जाता है:

{\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n{\bmod {d}}))\left(e_{d}\left(\left\lfloor {\frac {n}{d}}\right\rfloor \right)+1\right)

,^[8]

जहां s_d() n और e के मानक आधार-डी प्रतिनिधित्व के सभी अंकों का योग है (n) n_d इसके गुणन में d घातांक है।

इससे यह कम हो जाता है

2n-2s_{2}(n)-e_{2}(n)

,^[8]d = 2, और के लिए

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 31: / Line 31: @@
 == डेटा संरचना ==
-{{math|''d''}}-एरी हीप में एक ऐरे डेटा संरचना होती है {{math|''n''}}, जिनमें से प्रत्येक के साथ एक प्राथमिकता जुड़ी हुई होती है। इन पदोंं को संपूर्ण रूप से नोड्स के रूप में देखा जा सकता है {{math|''d''}}-एरी ट्री,: सरणी की स्थिति 0 पर (शून्य-आधारित नंबरिंग का उपयोग करके) ट्री बनाता है, स्थिति 1 से लेकर {{math|''d''}} तक इसके चाइल्ड नोड होते है इस प्रकार, स्थिति में पद {{math|''i''}} (इसके लिए {{math|''i'' > 0}}) स्थिति पर पद है {{math|{{floor|(''i'' &minus; 1)/''d''}}}} और उसके चाइल्ड पदों पर पद है {{math|''di'' + 1}} द्वारा {{math|''di'' + ''d''}}. बाइनरी हीप के अनुसार, मिन-हीप में, प्रत्येक पद की एक प्राथमिकता होती है जो कम से कम उसके मूल के बराबर बड़ी होती है, अधिकतम-हीप में, प्रत्येक पद की एक प्राथमिकता होती है जो उसके मूल से बड़ी नहीं होती है।<ref name="t83">{{citation
+{{math|''d''}}-एरी हीप में {{math|''n''}} वस्तु की एक श्रृंखला होती है,जिनमें से प्रत्येक के साथ एक प्राथमिकता जुड़ी होती है। इन वस्तुओं को संपूर्ण {{math|''d''}}-एरी ट्री, में नोड्स के रूप में देखा जा सकता है, जो चौड़ाई के पहले ट्रैवर्सल क्रम में सूचीबद्ध हैं: सरणी की स्थिति 0 पर वस्तुओं (शून्य-आधारित नंबरिंग का उपयोग करके) ट्री की जड़ बनाता है, स्थिति 1 से लेकर {{math|''d''}} तक इसके चाइल्ड नोड होते है इस प्रकार, स्थिति  {{math|''i''}} (किसी भी {{math|''i'' > 0}} के लिए) पर वस्तुओं का मूल तत्व स्थिति {{math|{{floor|(''i'' &minus; 1)/''d''}}}} और उसके चाइल्ड पदों पर {{math|''di'' + 1}} द्वारा {{math|''di'' + ''d''}} स्थिति पर वस्तु होती हैं। बाइनरी हीप के अनुसार, मिन-हीप में, प्रत्येक पद की एक प्राथमिकता होती है जो कम से कम उसके मूल के बराबर बड़ी होती है, अधिकतम-हीप में, प्रत्येक वस्तुओ की एक प्राथमिकता होती है जो उसके मूल से बड़ी नहीं होती है।<ref name="t83">{{citation
   | last = Tarjan | first = R. E. | author-link = Robert Tarjan
   | contribution = 3.2. ''d''-heaps
@@ Line 47: / Line 47: @@
 किसी सारणी से एक नया हीप बनाने के लिए {{math|''n''}}, पद की स्थिति से प्रारंभ करते हुए, रिवर्स ऑर्डर में पद पर लूप कर सकता है {{math|''n'' &minus; 1}} और पद को स्थिति 0 पर समाप्त करते हुए, प्रत्येक पद के लिए डाउनवर्ड-स्वैपिंग प्रक्रिया को प्रारंभ करता है।<ref name="t83" /><ref name="w07" />
 ==विश्लेषण==
-एक {{math|''d''}}-एरी हीप के साथ {{math|''n''}} पद, ऊपर की ओर-स्वैपिंग प्रक्रिया और नीचे की ओर-स्वैपिंग प्रक्रिया दोनों ही कार्य कर सकते है {{math|1=log<sub>''d''</sub> ''n'' = log ''n'' / log ''d''}}। अपवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप में किसी पद की उसके मूल के साथ एकल तुलना सम्मलित होती है, और इसमें निरंतर समय लगता है। इसलिए, हीप में एक नया पद डालने, न्यूनतम-हीप में किसी पद की प्राथमिकता को कम करने, या अधिकतम-हीप में किसी पद की प्राथमिकता बढ़ाने का समय है {{math|O(log ''n'' / log ''d'')}}. डाउनवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप सम्मलित होते है {{math|''d''}} और {{math|O(''d'')}} समय लगता है {{math|''d'' &minus; 1}} चाइल्ड की न्यूनतम या अधिकतम संख्या निर्धारित करने के लिए चाइल्ड नोड के विरुद्ध अदला-बदली की आवश्यकता होती है। इसलिए, रूट पद को हटाने, न्यूनतम-हीप में किसी पद की प्राथमिकता बढ़ाने या अधिकतम-हीप में किसी पद की प्राथमिकता कम करने का समय है {{math|O(''d'' log ''n'' / log ''d'')}}.<ref name="t83"/><ref name="w07"/>
+एक {{math|''d''}}-एरी हीप के साथ {{math|''n''}} पद, ऊपर की ओर-स्वैपिंग प्रक्रिया और नीचे की ओर-स्वैपिंग प्रक्रिया दोनों ही कार्य कर सकते है {{math|1=log<sub>''d''</sub> ''n'' = log ''n'' / log ''d''}}। अपवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप में किसी पद की उसके मूल के साथ एकल तुलना सम्मलित होती है, और इसमें निरंतर समय लगता है। इसलिए, हीप में एक नया विषय डालने, न्यूनतम-हीप में किसी पद की प्राथमिकता को कम करने, या अधिकतम-हीप में किसी पद की प्राथमिकता बढ़ाने का समय है {{math|O(log ''n'' / log ''d'')}}. डाउनवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप सम्मलित होते है {{math|''d''}} और {{math|O(''d'')}} समय लगता है {{math|''d'' &minus; 1}} चाइल्ड की न्यूनतम या अधिकतम संख्या निर्धारित करने के लिए चाइल्ड नोड के विरुद्ध अदला-बदली की आवश्यकता होती है। इसलिए, रूट पद को हटाने, न्यूनतम-हीप में किसी पद की प्राथमिकता बढ़ाने या अधिकतम-हीप में किसी पद की प्राथमिकता कम करने का समय है {{math|O(''d'' log ''n'' / log ''d'')}}<ref name="t83"/><ref name="w07"/>
-{{math|''d''}}-एन पदोंं के एक सेट हीप, अधिकांश पद ऐसी स्थिति में होता है जो अंततः ट्री को प्राप्त करता है {{math|''d''}}-एरी ट्री, और उन पदोंं के लिए कोई नीचे की ओर स्वैपिंग नहीं की जाती है। अधिक से अधिक {{math|''n''/''d'' + 1}} पद गैर-ट्री होते है, और इन्हें कम से कम एक बार नीचे की ओर बदला जा सकता है {{math|O(''d'')}} उनकी अदला-बदली के लिए चाइल्ड को प्राप्त किया जाता है। अधिक से अधिक {{math|''n''/''d''<sup>2</sup> + 1}} नोड्स को दो बार नीचे की ओर स्वैप किया जा सकता है, जिससे अतिरिक्त समय होता है {{math|O(''d'')}} दूसरे स्वैप के पहले से ही गणना का समय अधिक होता है। इसलिए, इस तरह से हीप बनाने में लगने वाला कुल समय है
+{{math|''d''}}-एन पदोंं के एक सममुच्च हीप, अधिकांश पद ऐसी स्थिति में होता है, जो अंततः ट्री को प्राप्त करता है {{math|''d''}}-एरी ट्री, और उन वस्तुओ के लिए कोई नीचे की ओर स्वैपिंग नहीं की जाती है। अधिक से अधिक {{math|''n''/''d'' + 1}} पद गैर-ट्री होते है, और इन्हें कम से कम एक बार नीचे की ओर बदला जा सकता है {{math|O(''d'')}} उनकी अदला-बदली के लिए चाइल्ड को प्राप्त किया जाता है। अधिक से अधिक {{math|''n''/''d''<sup>2</sup> + 1}} नोड्स को दो बार नीचे की ओर स्वैप किया जा सकता है, जिससे अतिरिक्त समय होता है {{math|O(''d'')}} दूसरे स्वैप के पहले से ही गणना का समय अधिक होता है। इसलिए, इस तरह से हीप बनाने में लगने वाला कुल समय होता है।
 :<math>\sum_{i=1}^{\log_d n} \left(\frac{n}{d^i}+1\right) O(d) = O(n).</math><ref name="t83"/><ref name="w07"/>
-उपरोक्त का त्रुटिहीन मान (डी-एरी हीप के निर्माण के समय तुलना की सबसे कठिन स्थिति वाली संख्या) को इसके बराबर माना जाता है:
+उपरोक्त का त्रुटिहीन मान ({{math|''d''}}-एरी हीप के निर्माण के समय तुलना की सबसे कठिन स्थिति वाली संख्या) को इसके बराबर माना जाता है:
 :<math> \frac{d}{d-1} (n - s_d (n)) - (d-1 - (n  \bmod  d)) \left( e_d \left( \left\lfloor \frac{n}{d} \right\rfloor\right) + 1\right) </math>,<ref name="Suchenek">{{citation

Anonymous

Search

डी-एरी हीप: Difference between revisions

Namespaces

More

Page actions

Revision as of 01:19, 4 August 2023

Contents

डेटा संरचना

विश्लेषण