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

From Vigyanwiki
(Created page with "{{DISPLAYTITLE:''d''-ary heap}} {{math|''d''}}-एरी ढेर या{{math|''d''}}-हीप एक प्राथमिकता कतार डेटा सं...")
 
No edit summary
 
(16 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{DISPLAYTITLE:''d''-ary heap}}
{{DISPLAYTITLE:''d''-ary heap}}
{{math|''d''}}-एरी ढेर या{{math|''d''}}-हीप एक [[प्राथमिकता कतार]] [[डेटा संरचना]] है, जो [[ बाइनरी ढेर ]] का एक सामान्यीकरण है जिसमें नोड्स होते हैं {{math|''d''}} 2 के बजाय बच्चे।<ref name="j75"/><ref name="t83"/><ref name="w07"/>इस प्रकार, एक बाइनरी ढेर 2-ढेर है, और एक टर्नरी ढेर 3-ढेर है। टारजन के अनुसार<ref name="t83"/>और जेन्सेन एट अल.,<ref>{{citation
 
'''{{math|''d''}}-एरी हीप या {{math|''d''}}-हीप''' एक [[प्राथमिकता कतार|प्राथमिक]] [[डेटा संरचना]] होती है, जो [[ बाइनरी ढेर |बाइनरी हीप]] का एक सामान्यीकरण होता है जिसमें नोड्स मे 2 के अतिरिक्त {{math|''d''}} चिल्ड्रेन होते है।<ref name="j75"/><ref name="t83"/><ref name="w07"/> इस प्रकार, एक बाइनरी हीप मे 2-हीप और एक टर्नरी हीप मे 3-हीप होते है। टारजन <ref name="t83"/>और जेन्सेन एट अल के अनुसार,<ref>{{citation
  | last1 = Jensen | first1 = C.
  | last1 = Jensen | first1 = C.
  | last2 = Katajainen | first2 = J.
  | last2 = Katajainen | first2 = J.
Line 14: Line 15:
  | volume = 4
  | volume = 4
  | year = 1975
  | year = 1975
  | issue = 3}}.</ref>
  | issue = 3}}.</ref>  
यह डेटा संरचना धीमी प्राथमिकता वाले ऑपरेशनों को बाइनरी हीप्स की तुलना में अधिक तेज़ी से निष्पादित करने की अनुमति देती है, धीमे डिलीट न्यूनतम ऑपरेशन की कीमत पर। यह ट्रेडऑफ़ दिज्क्स्ट्रा के एल्गोरिदम जैसे एल्गोरिदम के लिए बेहतर चलने वाले समय की ओर ले जाता है जिसमें प्राथमिकता वाले ऑपरेशन डिलीट मिन ऑपरेशंस की तुलना में अधिक सामान्य होते हैं।<ref name="j75"/><ref name="t2"/>इसके अतिरिक्त, {{math|''d''}}-एरी हीप्स में बाइनरी हीप्स की तुलना में बेहतर [[मेमोरी कैश]] व्यवहार होता है, जो उन्हें सैद्धांतिक रूप से बड़े सबसे खराब स्थिति वाले रनिंग टाइम के बावजूद व्यवहार में अधिक तेज़ी से चलाने की अनुमति देता है।<ref name="nmm91"/>बाइनरी ढेर की तरह, {{math|''d''}}-एरी हीप्स एक [[ इन-प्लेस एल्गोरिदम ]]|इन-प्लेस डेटा संरचना है जो हीप में आइटमों की श्रृंखला को संग्रहीत करने के लिए आवश्यक अतिरिक्त भंडारण का उपयोग नहीं करती है।<ref name="t83"/><ref name="mp05">{{citation
 
यह डेटा संरचना धीमी प्राथमिकता वाले संक्रिया बहुकार्य को बाइनरी हीप्स की तुलना में अधिक तेज़ी से निष्पादित करने की अनुमति देती है, धीमी गति की कीमत पर न्यूनतम संचालन हटाएं जाते है। यह ट्रेडऑफ़ दिज्क्स्ट्रा के एल्गोरिदम के लिए अच्छा  चलन समय की ओर ले जाता है, जिसमें प्राथमिकता वाले संक्रिया बहुकार्य डिलीट मिन संक्रिया बहुकार्य की तुलना में अधिक सामान्य होते है।<ref name="j75" /><ref name="t2" /> इसके अतिरिक्त, {{math|''d''}}-एरी हीप्स में बाइनरी हीप्स की तुलना में अच्छा  [[मेमोरी कैश]] व्यवहार होता है, जो उन्हें सैद्धांतिक रूप से बड़े कठिन स्थिति वाले रनिंग टाइम के अतिरिक्त व्यवहार में अधिक तेजी लाने की अनुमति देता है।<ref name="nmm91" /> बाइनरी हीप की तरह, {{math|''d''}}-एरी हीप्स एक [[ इन-प्लेस एल्गोरिदम |इन-प्लेस]] डेटा संरचना होती है जो हीप की श्रृंखलाओं को संग्रहीत करने के लिए आवश्यक अतिरिक्त स्टॉरिज का उपयोग नहीं करती है। <ref name="t83" /><ref name="mp05">{{citation
  | last1 = Mortensen | first1 = C. W.
  | last1 = Mortensen | first1 = C. W.
  | last2 = Pettie | first2 = S.
  | last2 = Pettie | first2 = S.
Line 28: Line 30:
  | isbn = 978-3-540-28101-6}}.</ref>
  | isbn = 978-3-540-28101-6}}.</ref>


 
== डेटा संरचना ==
==डेटा संरचना== {{math|''d''}}}-एरी हीप में एक ऐरे डेटा संरचना होती है {{math|''n''}} आइटम, जिनमें से प्रत्येक के साथ एक प्राथमिकता जुड़ी हुई है। इन वस्तुओं को संपूर्ण रूप से नोड्स के रूप में देखा जा सकता है {{math|''d''}}-एरी ट्री, चौड़ाई-पहली खोज में सूचीबद्ध: सरणी की स्थिति 0 पर आइटम (शून्य-आधारित नंबरिंग का उपयोग करके) पेड़ की जड़ बनाता है, स्थिति 1 से लेकर आइटम तक {{math|''d''}} इसके बच्चे हैं, अगले {{math|''d''<sup>2</sup>}} वस्तुएँ उसके पोते आदि हैं। इस प्रकार, स्थिति में वस्तु का जनक {{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
  | last = Tarjan | first = R. E. | author-link = Robert Tarjan
  | contribution = 3.2. ''d''-heaps
  | contribution = 3.2. ''d''-heaps
Line 37: Line 39:
  | title = Data Structures and Network Algorithms
  | title = Data Structures and Network Algorithms
  | volume = 44
  | volume = 44
  | year = 1983}}. Note that Tarjan uses 1-based numbering, not 0-based numbering, so his formulas for the parent and children of a node need to be adjusted when 0-based numbering is used.</ref><ref name="w07"/>
  | year = 1983}}. Note that Tarjan uses 1-based numbering, not 0-based numbering, so his formulas for the parent and children of a node need to be adjusted when 0-based numbering is used.</ref><ref name="w07" />


न्यूनतम-हीप में न्यूनतम प्राथमिकता वाला आइटम (या अधिकतम-हीप में अधिकतम प्राथमिकता वाला आइटम) हमेशा सरणी के स्थान 0 पर पाया जा सकता है। इस आइटम को प्राथमिकता कतार से हटाने के लिए, सरणी में अंतिम आइटम x को उसके स्थान पर ले जाया जाता है, और सरणी की लंबाई एक से कम कर दी जाती है। फिर, जबकि आइटम x और उसके बच्चे ढेर संपत्ति को संतुष्ट नहीं करते हैं, आइटम x को उसके बच्चों में से एक के साथ बदल दिया जाता है (मिन-हीप में सबसे छोटी प्राथमिकता वाला, या अधिकतम-हीप में सबसे बड़ी प्राथमिकता वाला) , इसे पेड़ में और बाद में सरणी में नीचे की ओर ले जाना, जब तक कि अंततः ढेर संपत्ति संतुष्ट न हो जाए। उसी डाउनवर्ड स्वैपिंग प्रक्रिया का उपयोग न्यूनतम-ढेर में किसी आइटम की प्राथमिकता को बढ़ाने के लिए, या अधिकतम-ढेर में किसी आइटम की प्राथमिकता को कम करने के लिए किया जा सकता है।<ref name="t83"/><ref name="w07"/>
न्यूनतम-हीप में न्यूनतम प्राथमिकता वाले पद (या अधिकतम-हीप में अधिकतम प्राथमिकता वाले पद) हमेशा सरणी के स्थान 0 पर प्राप्त किया जा सकता है। इस पद को प्राथमिकता से हटाने के लिए, सरणी में अंतिम पद x को उसके स्थान पर ले जाया जाता है, और सरणी की लंबाई को एक से कम कर दी जाती है। फिर, जबकि पद x और उसके चाइल्ड हीप होते है, पद x को उसके चाइल्ड हीप में से एक के साथ बदल दिया जाता है (मिन-हीप में सबसे छोटी प्राथमिकता होती है, या अधिकतम-हीप में सबसे बड़ी प्राथमिकता होती है) , इसे ट्री में और बाद में सरणी में नीचे की ओर ले जाते है। उसी डाउनवर्ड स्वैपिंग प्रक्रिया का उपयोग न्यूनतम-हीप में पद की प्राथमिकता को बढ़ाने के लिए, या अधिकतम-हीप में किसी पद की प्राथमिकता को कम करने के लिए किया जा सकता है।<ref name="t83" /><ref name="w07" />
 
ढेर में एक नया आइटम डालने के लिए, आइटम को सरणी के अंत में जोड़ा जाता है, और फिर जब ढेर संपत्ति का उल्लंघन होता है तो इसे अपने मूल के साथ बदल दिया जाता है, इसे पेड़ में ऊपर की ओर और सरणी में पहले ले जाया जाता है, जब तक कि अंततः ढेर संपत्ति संतुष्ट है. उसी अपवर्ड-स्वैपिंग प्रक्रिया का उपयोग न्यूनतम-ढेर में किसी आइटम की प्राथमिकता को कम करने, या अधिकतम-ढेर में किसी आइटम की प्राथमिकता को बढ़ाने के लिए किया जा सकता है।<ref name="t83"/><ref name="w07"/>
 
किसी सारणी से एक नया ढेर बनाने के लिए {{math|''n''}} आइटम, कोई आइटम की स्थिति से शुरू करते हुए, रिवर्स ऑर्डर में आइटम पर लूप कर सकता है {{math|''n'' &minus; 1}} और आइटम को स्थिति 0 पर समाप्त करते हुए, प्रत्येक आइटम के लिए डाउनवर्ड-स्वैपिंग प्रक्रिया को लागू करना।<ref name="t83"/><ref name="w07"/>


हीप में एक नया पद डालने के लिए, पद को सरणी के अंत में जोड़ा जाता है, और फिर जब हीप का उल्लंघन होता है तो इसे अपने मूल के साथ बदल दिया जाता है, इसे ट्री में ऊपर की ओर और सरणी में पहले ले जाया जाता है उसी अपवर्ड-स्वैपिंग प्रक्रिया का उपयोग न्यूनतम-हीप में किसी पद की प्राथमिकता को कम करने, या अधिकतम-हीप में किसी पद की प्राथमिकता को बढ़ाने के लिए किया जा सकता है।<ref name="t83" /><ref name="w07" />


किसी {{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>\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
:<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
Line 65: Line 65:
  | year = 2012
  | year = 2012
  | url = http://www.deepdyve.com/lp/ios-press/elementary-yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU}}.</ref>
  | url = http://www.deepdyve.com/lp/ios-press/elementary-yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU}}.</ref>
कहाँ एस<sub>d</sub>(एन) एन और के मानक आधार-डी प्रतिनिधित्व के सभी अंकों का योग है<sub>d</sub>(n) n के गुणनखंडन में d का घातांक है।
जहां s<sub>d</sub>() n और e के मानक आधार-डी प्रतिनिधित्व के सभी अंकों का योग है (n) n<sub>d</sub> इसके गुणन में d घातांक है।
 
इससे यह कम हो जाता है
इससे यह कम हो जाता है
:<math> 2 n - 2 s_2 (n) - e_2 (n) </math>,<ref name="Suchenek" />d = 2, और के लिए
:<math> 2 n - 2 s_2 (n) - e_2 (n) </math>,<ref name="Suchenek" />d = 2, और के लिए
Line 72: Line 73:
डी = 3 के लिए.
डी = 3 के लिए.


का स्थान उपयोग {{math|''d''-ary}} हीप, इन्सर्ट और डिलीट-मिन ऑपरेशंस के साथ, रैखिक है, क्योंकि यह हीप में आइटमों की सूची वाली सरणी के अलावा किसी अतिरिक्त भंडारण का उपयोग नहीं करता है।<ref name="t83"/><ref name="mp05"/>यदि मौजूदा वस्तुओं की प्राथमिकताओं में परिवर्तन का समर्थन करने की आवश्यकता है, तो किसी को वस्तुओं से ढेर में उनकी स्थिति तक पॉइंटर्स भी बनाए रखना होगा, जो फिर से केवल रैखिक भंडारण का उपयोग करता है।<ref name="t83"/>
इस स्थान का उपयोग {{math|''d''-ary}} हीप, इन्सर्ट और डिलीट-मिन संक्रिया बहुकार्य के साथ, रैखिक है, क्योंकि यह हीप में पदों की सूची वाली सरणी के अतिरिक्त किसी अतिरिक्त स्टोरेज का उपयोग नहीं करता है।<ref name="t83"/><ref name="mp05"/> यदि उपस्थित पदोंं की प्राथमिकताओं में परिवर्तन का समर्थन करने की आवश्यकता है, तो पदोंं से हीप में उनकी स्थिति तक पॉइंटर्स भी बनाए रखना होता है, जो केवल रैखिक स्टोरेज का उपयोग करता है।<ref name="t83"/>
 
 
==अनुप्रयोग==
==अनुप्रयोग==
[[ग्राफ़ (अलग गणित)]] पर काम करते समय {{mvar|m}}किनारे और {{mvar|n}} कोने, सबसे छोटे पथों के लिए दिज्क्स्ट्रा का एल्गोरिदम और न्यूनतम फैले हुए पेड़ों के लिए प्राइम का एल्गोरिदम दोनों एक न्यूनतम-ढेर का उपयोग करते हैं जिसमें हैं {{math|''n''}} डिलीट-मिन ऑपरेशंस और उतने ही {{mvar|m}} कमी-प्राथमिकता संचालन। ए का उपयोग करके {{mvar|d}}-एरी ढेर के साथ {{math|1=''d'' = ''m''/''n''}}, इन दो प्रकार के परिचालनों के लिए कुल समय को एक-दूसरे के विरुद्ध संतुलित किया जा सकता है, जिससे कुल समय प्राप्त हो सकता है {{math|O(''m'' log<sub>''m''/''n''</sub> ''n'')}} एल्गोरिथम के लिए, में सुधार {{math|O(''m'' log ''n'')}} जब भी किनारों की संख्या शीर्षों की संख्या से काफी बड़ी होती है, तो इन एल्गोरिदम के बाइनरी हीप संस्करणों का चलने का समय।<ref name="j75"/><ref name="t2">{{harvtxt|Tarjan|1983}}, pp. 77 and 91.</ref> एक वैकल्पिक प्राथमिकता कतार डेटा संरचना, फाइबोनैचि हीप, और भी बेहतर सैद्धांतिक चलने का समय देता है {{math|O(''m'' + ''n'' log ''n'')}}, लेकिन व्यवहार में {{mvar|d}}-एरी हीप्स आम तौर पर इस एप्लिकेशन के लिए फाइबोनैचि हीप्स की तुलना में कम से कम तेज़ और अक्सर तेज़ होते हैं।<ref>{{citation
[[ग्राफ़ (अलग गणित)|ग्राफ़ (गणित)]] पर काम करते समय {{mvar|m}} किनारे और {{mvar|n}} कोने में, सबसे छोटे पथों के लिए दिज्क्स्ट्रा का एल्गोरिदम और न्यूनतम फैले हुए ट्री के लिए मुख्य एल्गोरिदम दोनों मिन-हीप का उपयोग करते हैं जिसमें {{math|''n''}} डिलीट-मिन संक्रिया बहुकार्य और {{mvar|m}} प्राथमिकता संचालन होते हैं।  {{math|1=''d'' = ''m''/''n''}} के साथ  {{mvar|d}}-एरी हीप का उपयोग करके, इन दो प्रकार के संक्रिया बहुकार्यों के लिए कुल समय को एक दूसरे के विरुद्ध संतुलित किया जा सकता है, जिससे एल्गोरिदम के लिए {{math|O(''m'' log<sub>''m''/''n''</sub> ''n'')}} का कुल समय हो सकता है, जब भी किनारों की संख्या कोने की संख्या से अधिक बड़ी होती है, तो इन एल्गोरिदम के बाइनरी हीप संस्करणों का {{math|O(''m'' log ''n'')}} चलन समय होता है।<ref name="j75"/><ref name="t2">{{harvtxt|Tarjan|1983}}, pp. 77 and 91.</ref> एक वैकल्पिक प्राथमिकता डेटा संरचना, फाइबोनैचि हीप, {{math|O(''m'' + ''n'' log ''n'')}} का और भी सैद्धांतिक चलन समय देता है, किन्तु  प्राचलन पद्धति में {{mvar|d}}-एरी हीप सामान्यतः इस एप्लिकेशन के लिए फाइबोनैचि हीप्स की तुलना में अधिकांशतः तेज़ होते है।<ref>{{citation
  | last1 = Cherkassky | first1 = Boris V.
  | last1 = Cherkassky | first1 = Boris V.
  | last2 = Goldberg | first2 = Andrew V. | author2-link = Andrew V. Goldberg
  | last2 = Goldberg | first2 = Andrew V. | author2-link = Andrew V. Goldberg
Line 90: Line 89:
  | url = ftp://www-cs-staff.stanford.edu/cs/theory/goldberg/stan-cs-93-1480.ps.gz#
  | url = ftp://www-cs-staff.stanford.edu/cs/theory/goldberg/stan-cs-93-1480.ps.gz#
}}.</ref>
}}.</ref>
व्यवहार में 4-हीप्स बाइनरी हीप्स से बेहतर प्रदर्शन कर सकते हैं, यहां तक ​​कि डिलीट-मिन ऑपरेशन के लिए भी।<ref name="t83"/><ref name="w07">{{citation
 
प्राचलन पद्धति में 4-हीप्स बाइनरी हीप्स से अच्छा प्रदर्शन कर सकते है, यहां तक ​​कि डिलीट-मिन संक्रिया बहुकार्य के लिए भी अच्छा प्रदर्शन कर सकते है।<ref name="t83" /><ref name="w07">{{citation
  | last = Weiss | first = M. A.
  | last = Weiss | first = M. A.
  | contribution = ''d''-heaps
  | contribution = ''d''-heaps
Line 98: Line 98:
  | publisher = Addison-Wesley
  | publisher = Addison-Wesley
  | title = Data Structures and Algorithm Analysis
  | title = Data Structures and Algorithm Analysis
  | year = 2007}}.</ref> इसके अतिरिक्त,
  | year = 2007}}.</ref> इसके अतिरिक्त, एक  {{mvar|d}}-एरी हीप सामान्यतः कंप्यूटर की [[कैश मैमोरी]] के आकार से अधिक हीप आकारों के लिए बाइनरी हीप की तुलना में बहुत तेजी से चलता है: एक बाइनरी हीप के लिए सामान्यतः कंप्यूटर की [[कैश मिस]] और [[ आभासी मेमोरी |आभासी मेमोरी]] पेज दोष की आवश्यकता होती है प्रत्येक बाइनरी हीप की तुलना में  {{mvar|d}}-एरीहीप द्वारा की गई अतिरिक्त तुलनाओं द्वारा किए गए अतिरिक्त कार्य की तुलना में कहीं अधिक समय लगता है।<ref name="nmm91">{{citation
{{mvar|d}}-एरी हीप आम तौर पर कंप्यूटर की [[कैश मैमोरी]] के आकार से अधिक के हीप आकारों के लिए बाइनरी हीप की तुलना में बहुत तेजी से चलता है:
एक बाइनरी हीप के लिए आम तौर पर एक की तुलना में अधिक [[कैश मिस]] और [[ आभासी मेमोरी ]] पेज दोष की आवश्यकता होती है {{mvar|d}}-एरी ढेर, प्रत्येक अतिरिक्त तुलना द्वारा किए गए अतिरिक्त कार्य की तुलना में कहीं अधिक समय लेता है {{mvar|d}}-एरी हीप की तुलना बाइनरी हीप से की जाती है।<ref name="nmm91">{{citation
  | last1 = Naor | first1 = D.
  | last1 = Naor | first1 = D.
  | last2 = Martel | first2 = C. U.
  | last2 = Martel | first2 = C. U.
Line 120: Line 118:
  | issue = 6
  | issue = 6
  | date = 11 June 2010}}.</ref>
  | date = 11 June 2010}}.</ref>
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
Line 129: Line 125:
*[https://github.com/valyala/gheap C++ implementation of generalized heap with D-Heap support]
*[https://github.com/valyala/gheap C++ implementation of generalized heap with D-Heap support]


{{DEFAULTSORT:D-Ary Heap}}[[Category: ढेर (डेटा संरचनाएं)]]
{{DEFAULTSORT:D-Ary Heap}}
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023|D-Ary Heap]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page|D-Ary Heap]]
[[Category:Pages with ignored display titles]]
[[Category:Pages with script errors|D-Ary Heap]]
[[Category:Templates Vigyan Ready|D-Ary Heap]]
[[Category:ढेर (डेटा संरचनाएं)|D-Ary Heap]]

Latest revision as of 15:15, 10 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 पद, ऊपर की ओर-स्वैपिंग प्रक्रिया और नीचे की ओर-स्वैपिंग प्रक्रिया दोनों ही कार्य कर सकते है logd 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/d2 + 1 नोड्स को दो बार नीचे की ओर स्वैप किया जा सकता है, जिससे अतिरिक्त समय होता है O(d) दूसरे स्वैप के पहले से ही गणना का समय अधिक होता है। इसलिए, इस तरह से हीप बनाने में लगने वाला कुल समय होता है।

[2][3]

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

,[8]

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

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

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

डी = 3 के लिए.

इस स्थान का उपयोग d-ary हीप, इन्सर्ट और डिलीट-मिन संक्रिया बहुकार्य के साथ, रैखिक है, क्योंकि यह हीप में पदों की सूची वाली सरणी के अतिरिक्त किसी अतिरिक्त स्टोरेज का उपयोग नहीं करता है।[2][7] यदि उपस्थित पदोंं की प्राथमिकताओं में परिवर्तन का समर्थन करने की आवश्यकता है, तो पदोंं से हीप में उनकी स्थिति तक पॉइंटर्स भी बनाए रखना होता है, जो केवल रैखिक स्टोरेज का उपयोग करता है।[2]

अनुप्रयोग

ग्राफ़ (गणित) पर काम करते समय m किनारे और n कोने में, सबसे छोटे पथों के लिए दिज्क्स्ट्रा का एल्गोरिदम और न्यूनतम फैले हुए ट्री के लिए मुख्य एल्गोरिदम दोनों मिन-हीप का उपयोग करते हैं जिसमें n डिलीट-मिन संक्रिया बहुकार्य और m प्राथमिकता संचालन होते हैं। d = m/n के साथ d-एरी हीप का उपयोग करके, इन दो प्रकार के संक्रिया बहुकार्यों के लिए कुल समय को एक दूसरे के विरुद्ध संतुलित किया जा सकता है, जिससे एल्गोरिदम के लिए O(m logm/n n) का कुल समय हो सकता है, जब भी किनारों की संख्या कोने की संख्या से अधिक बड़ी होती है, तो इन एल्गोरिदम के बाइनरी हीप संस्करणों का O(m log n) चलन समय होता है।[1][5] एक वैकल्पिक प्राथमिकता डेटा संरचना, फाइबोनैचि हीप, O(m + n log n) का और भी सैद्धांतिक चलन समय देता है, किन्तु प्राचलन पद्धति में d-एरी हीप सामान्यतः इस एप्लिकेशन के लिए फाइबोनैचि हीप्स की तुलना में अधिकांशतः तेज़ होते है।[9]

प्राचलन पद्धति में 4-हीप्स बाइनरी हीप्स से अच्छा प्रदर्शन कर सकते है, यहां तक ​​कि डिलीट-मिन संक्रिया बहुकार्य के लिए भी अच्छा प्रदर्शन कर सकते है।[2][3] इसके अतिरिक्त, एक d-एरी हीप सामान्यतः कंप्यूटर की कैश मैमोरी के आकार से अधिक हीप आकारों के लिए बाइनरी हीप की तुलना में बहुत तेजी से चलता है: एक बाइनरी हीप के लिए सामान्यतः कंप्यूटर की कैश मिस और आभासी मेमोरी पेज दोष की आवश्यकता होती है प्रत्येक बाइनरी हीप की तुलना में d-एरीहीप द्वारा की गई अतिरिक्त तुलनाओं द्वारा किए गए अतिरिक्त कार्य की तुलना में कहीं अधिक समय लगता है।[6][10]

संदर्भ

  1. 1.0 1.1 1.2 1.3 Johnson, D. B. (1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, doi:10.1016/0020-0190(75)90001-0.
  2. 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 2.11 Tarjan, R. E. (1983), "3.2. d-heaps", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 34–38. Note that Tarjan uses 1-based numbering, not 0-based numbering, so his formulas for the parent and children of a node need to be adjusted when 0-based numbering is used.
  3. 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 Weiss, M. A. (2007), "d-heaps", Data Structures and Algorithm Analysis (2nd ed.), Addison-Wesley, p. 216, ISBN 0-321-37013-9.
  4. Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF).
  5. 5.0 5.1 Tarjan (1983), pp. 77 and 91.
  6. 6.0 6.1 Naor, D.; Martel, C. U.; Matloff, N. S. (October 1991), "Performance of priority queue structures in a virtual memory environment", Computer Journal, 34 (5): 428–437, doi:10.1093/comjnl/34.5.428.
  7. 7.0 7.1 Mortensen, C. W.; Pettie, S. (2005), "The complexity of implicit and space efficient priority queues", Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3608, Springer-Verlag, pp. 49–60, doi:10.1007/11534273_6, ISBN 978-3-540-28101-6.
  8. 8.0 8.1 8.2 Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751.
  9. Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (May 1996), "Shortest paths algorithms: Theory and experimental evaluation", Mathematical Programming, 73 (2): 129–174, CiteSeerX 10.1.1.48.752, doi:10.1007/BF02592101.
  10. Kamp, Poul-Henning (11 June 2010), "You're doing it wrong", ACM Queue, 8 (6).


बाहरी संबंध