मिन-मैक्स हीप: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 11: Line 11:
}}
}}


[[कंप्यूटर विज्ञान]] में, न्यूनतम-अधिकतम हीप पूर्ण [[ द्विआधारी वृक्ष |बाइनरी ट्री]] [[डेटा संरचना]] है जो न्यूनतम-हीप और अधिकतम-हीप दोनों की उपयोगिता को जोड़ती है, अर्थात, यह न्यूनतम और अधिकतम दोनों अवयवों की निरंतर समय पुनर्प्राप्ति और लॉगरिदमिक समय निष्कासन प्रदान करती है।<ref name=":0">{{Cite journal|last1=ATKINSON|first1=M. D|last2=SACK|first2=J.-R|last3=SANTORO|first3=N.|last4=STROTHOTTE|first4=T.|year=1986|editor-last=Munro|editor-first=Ian|title=न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें|url=http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf|journal=Communications of the ACM|language=en|publication-date=1986|volume=29|issue=10|pages=996–1000|doi=10.1145/6617.6621|s2cid=3090797 }}</ref> यह डबल-एंड प्रायोरिटी क्यू को लागू करने के लिए न्यूनतम-अधिकतम हीप को बहुत ही उपयोगी डेटा संरचना बनाता है। बाइनरी न्यूनतम-हीप और अधिकतम-हीप के जैसे, न्यूनतम-अधिकतम हीप लॉगरिदमिक इन्सर्टेसन और डेलेसन का समर्थन करते हैं और रैखिक समय में बनाए जा सकते हैं।<ref>{{Cite journal|last1=ATKINSON|first1=M. D|last2=SACK|first2=J.-R|last3=SANTORO|first3=N.|last4=STROTHOTTE|first4=T.|year=1986|editor-last=Munro|editor-first=Ian|title=न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें|url=http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf|journal=Communications of the ACM|language=en|publication-date=1986|volume=29|issue=10|pages=996–1000|doi=10.1145/6617.6621|s2cid=3090797 }}</ref> न्यूनतम-अधिकतम हीप को प्रायः सरणी में इम्प्लिसिटी रूप से दर्शाया जाता है;<ref name=":1">{{Cite journal|last1=ATKINSON|first1=M. D|last2=SACK|first2=J.-R|last3=SANTORO|first3=N.|last4=STROTHOTTE|first4=T.|year=1986|editor-last=Munro|editor-first=Ian|title=न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें|url=http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf|journal=Communications of the ACM|language=en|publication-date=1986|volume=29|issue=10|pages=996–1000|doi=10.1145/6617.6621|s2cid=3090797 }}</ref> इसलिए इसे [[अंतर्निहित डेटा संरचना|इम्प्लिसिटी डेटा संरचना]] के रूप में जाना जाता है।
[[कंप्यूटर विज्ञान]] में, मिन-मैक्स हीप पूर्ण [[ द्विआधारी वृक्ष |बाइनरी ट्री]] [[डेटा संरचना]] है जो '''मिन-हीप''' और मैक्स-हीप दोनों की उपयोगिता को जोड़ती है, अर्थात, यह मिन और मैक्स दोनों अवयवों की निरंतर समय पुनर्प्राप्ति और लॉगरिदमिक समय निष्कासन प्रदान करती है।<ref name=":0">{{Cite journal|last1=ATKINSON|first1=M. D|last2=SACK|first2=J.-R|last3=SANTORO|first3=N.|last4=STROTHOTTE|first4=T.|year=1986|editor-last=Munro|editor-first=Ian|title=न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें|url=http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf|journal=Communications of the ACM|language=en|publication-date=1986|volume=29|issue=10|pages=996–1000|doi=10.1145/6617.6621|s2cid=3090797 }}</ref> अतः यह डबल-एंड प्रायोरिटी क्यू को लागू करने के लिए मिन-मैक्स हीप को बहुत ही उपयोगी डेटा संरचना बनाता है। बाइनरी मिन-हीप और मैक्स-हीप के जैसे, मिन-मैक्स हीप लॉगरिदमिक इन्सर्टेसन और डेलेसन का समर्थन करते हैं और रैखिक समय में बनाए जा सकते हैं।<ref>{{Cite journal|last1=ATKINSON|first1=M. D|last2=SACK|first2=J.-R|last3=SANTORO|first3=N.|last4=STROTHOTTE|first4=T.|year=1986|editor-last=Munro|editor-first=Ian|title=न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें|url=http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf|journal=Communications of the ACM|language=en|publication-date=1986|volume=29|issue=10|pages=996–1000|doi=10.1145/6617.6621|s2cid=3090797 }}</ref> मिन-मैक्स हीप को प्रायः सरणी में इम्प्लिसिटी रूप से दर्शाया जाता है;<ref name=":1">{{Cite journal|last1=ATKINSON|first1=M. D|last2=SACK|first2=J.-R|last3=SANTORO|first3=N.|last4=STROTHOTTE|first4=T.|year=1986|editor-last=Munro|editor-first=Ian|title=न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें|url=http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf|journal=Communications of the ACM|language=en|publication-date=1986|volume=29|issue=10|pages=996–1000|doi=10.1145/6617.6621|s2cid=3090797 }}</ref> इसलिए इसे [[अंतर्निहित डेटा संरचना|इम्प्लिसिटी डेटा संरचना]] के रूप में जाना जाता है।


न्यूनतम-अधिकतम हीप गुण है: ट्री में सम स्तर पर प्रत्येक नोड उसके सभी वंशजों से कम है, जबकि ट्री में विषम स्तर पर प्रत्येक नोड उसके सभी वंशजों से बड़ा है।<ref name=":1" />
इस प्रकार से मिन-मैक्स हीप गुण है: ट्री में सम स्तर पर प्रत्येक नोड उसके सभी वंशजों से कम है, जबकि ट्री में विषम स्तर पर प्रत्येक नोड उसके सभी वंशजों से बड़ा है।<ref name=":1" />


संरचना को अन्य क्रम-सांख्यिकी ऑपरेशन को कुशलतापूर्वक समर्थन देने के लिए भी सामान्यीकृत किया जा सकता है, जैसे कि <code>find-median</code>, <code>delete-median</code>,<ref name=":0" /><code>find(k)</code> (संरचना में kवां सबसे छोटा मान निर्धारित करें) और ऑपरेशन <code>delete(k)</code> (संरचना में kवां सबसे छोटा मान हटाएं), k के किसी निश्चित मान (या मानों के समूह) के लिए। इन अंतिम दो ऑपरेशनों को क्रमशः स्थिर और लघुगणकीय समय में कार्यान्वित किया जा सकता है। न्यूनतम-अधिकतम क्रमण की धारणा को अधिकतम या न्यूनतम-क्रमण के आधार पर अन्य संरचनाओं तक बढ़ाया जा सकता है, जैसे लेफ्टिस ट्री, डेटा संरचनाओं का नवीन (और अधिक शक्तिशाली) वर्ग उत्पन्न करते हैं।<ref name=":1" /> बाहरी क्विकसॉर्ट लागू करते समय न्यूनतम-अधिकतम हीप भी उपयोगी हो सकता है।<ref>{{Cite book |isbn = 0201416077|title = Handbook of Algorithms and Data Structures: In Pascal and C|last1 = Gonnet|first1 = Gaston H.|last2 = Baeza-Yates|first2 = Ricardo|year = 1991}}</ref>
अतः संरचना को अन्य क्रम-सांख्यिकी ऑपरेशन को कुशलतापूर्वक समर्थन देने के लिए भी सामान्यीकृत किया जा सकता है, जैसे कि <code>find-median</code>, <code>delete-median</code>,<ref name=":0" /><code>find(k)</code> (संरचना में kवां सबसे छोटा मान निर्धारित करें) और ऑपरेशन <code>delete(k)</code> (संरचना में kवां सबसे छोटा मान हटाएं), k के किसी निश्चित मान (या मानों के समूह) के लिए। इन अंतिम दो ऑपरेशनों को क्रमशः स्थिर और लघुगणकीय समय में कार्यान्वित किया जा सकता है। इस प्रकार से मिन-मैक्स क्रमण की धारणा को मैक्स या मिन-क्रमण के आधार पर अन्य संरचनाओं तक बढ़ाया जा सकता है, जैसे लेफ्टिस ट्री, डेटा संरचनाओं का नवीन (और अधिक शक्तिशाली) वर्ग उत्पन्न करते हैं।<ref name=":1" /> अतः बाहरी क्विकसॉर्ट लागू करते समय मिन-मैक्स हीप भी पूर्ण रूप से उपयोगी हो सकता है।<ref>{{Cite book |isbn = 0201416077|title = Handbook of Algorithms and Data Structures: In Pascal and C|last1 = Gonnet|first1 = Gaston H.|last2 = Baeza-Yates|first2 = Ricardo|year = 1991}}</ref>
== विवरण ==
== विवरण ==


*न्यूनतम-अधिकतम हीप पूर्ण बाइनरी ट्री है जिसमें वैकल्पिक न्यूनतम (या सम) और अधिकतम (या विषम) स्तर होते हैं। सम स्तर उदाहरण के लिए 0, 2, 4, आदि हैं, और विषम स्तर क्रमशः 1, 3, 5, आदि हैं। हम अगले बिंदुओं में मानते हैं कि मूल अवयव पहले स्तर पर है, अर्थात 0।
*मिन-मैक्स हीप पूर्ण बाइनरी ट्री है जिसमें वैकल्पिक मिन (या सम) और मैक्स (या विषम) स्तर होते हैं। इस प्रकार से सम स्तर उदाहरण के लिए 0, 2, 4, आदि हैं, और विषम स्तर क्रमशः 1, 3, 5, आदि हैं। हम अगले बिंदुओं में मानते हैं कि मूल अवयव पहले स्तर पर है, अर्थात 0।
[[File:Min-max heap.jpg|thumb|300px|न्यूनतम-अधिकतम हीप का उदाहरण]]
[[File:Min-max heap.jpg|thumb|300px|मिन-मैक्स हीप का उदाहरण]]


* न्यूनतम-अधिकतम हीप में प्रत्येक नोड में डेटा सदस्य (सामान्यतः कुंजी कहा जाता है) होता है जिसका मान न्यूनतम-अधिकतम हीप में नोड के क्रम को निर्धारित करने के लिए उपयोग किया जाता है।
* मिन-मैक्स हीप में प्रत्येक नोड में डेटा सदस्य (सामान्यतः कुंजी कहा जाता है) होता है जिसका मान मिन-मैक्स हीप में नोड के क्रम को निर्धारित करने के लिए पूर्ण रूप से उपयोग किया जाता है।


* मूल अवयव न्यूनतम-अधिकतम हीप में सबसे छोटा अवयव है।
* मूल अवयव मिन-मैक्स हीप में सबसे छोटा अवयव है।
* दूसरे स्तर के दो अवयवों में से एक, जो अधिकतम (या विषम) स्तर है, न्यूनतम-अधिकतम हीप में सबसे बड़ा अवयव है
* दूसरे स्तर के दो अवयवों में से एक है, जो मैक्स (या विषम) स्तर है, मिन-मैक्स हीप में सबसे बड़ा अवयव है।
* मान लीजिए <math>x</math> न्यूनतम-अधिकतम हीप में कोई नोड है।
* मान लीजिए <math>x</math> मिन-मैक्स हीप में कोई नोड है।
** यदि <math>x</math> न्यूनतम (या सम) स्तर पर है, तो रूट <math>x.key</math> के साथ उपट्री में सभी कुंजियों के बीच <math>x</math> न्यूनतम कुंजी है।
** यदि <math>x</math> मिन (या सम) स्तर पर है, तो रूट <math>x.key</math> के साथ उपट्री में सभी कुंजियों के बीच <math>x</math> मिन कुंजी है।
** यदि <math>x</math> अधिकतम (या विषम) स्तर पर है, तो रूट <math>x.key</math> के साथ उपट्री में सभी कुंजियों के बीच <math>x</math> अधिकतम कुंजी है।
** यदि <math>x</math> मैक्स (या विषम) स्तर पर है, तो रूट <math>x.key</math> के साथ उपट्री में सभी कुंजियों के बीच <math>x</math> मैक्स कुंजी है।
* न्यूनतम (अधिकतम) स्तर पर नोड को न्यूनतम (अधिकतम) नोड कहा जाता है।
* मिन (मैक्स) स्तर पर नोड को मिन (मैक्स) नोड कहा जाता है।


अधिकतम-न्यूनतम हीप को समान रूप से परिभाषित किया गया है; ऐसे हीप में, अधिकतम मान रूट पर संग्रहीत होता है, और सबसे छोटा मान रूट के बच्चों में से पर संग्रहीत होता है।<ref name=":1" />
इस प्रकार से मैक्स-मिन हीप को समान रूप से परिभाषित किया गया है; ऐसे हीप में, मैक्स मान रूट पर संग्रहीत होता है, और सबसे छोटा मान रूट के बच्चों में से पर संग्रहीत होता है।<ref name=":1" />
==ऑपरेशन ==
==ऑपरेशन ==


निम्नलिखित ऑपरेशनों में हम मानते हैं कि न्यूनतम-अधिकतम हीप को सरणी <code>A[1।।N]</code> में दर्शाया गया है; सरणी में <math>ith</math> स्थान हीप में स्तर <math>\lfloor \log i \rfloor</math> पर स्थित नोड के अनुरूप होगा।
इस प्रकार से निम्नलिखित ऑपरेशनों में हम मानते हैं कि मिन-मैक्स हीप को सरणी <code>A[1।।N]</code> में दर्शाया गया है; सरणी में <math>ith</math> स्थान हीप में स्तर <math>\lfloor \log i \rfloor</math> पर स्थित नोड के अनुरूप होगा।


=== बिल्ड ===
=== बिल्ड ===


न्यूनतम-अधिकतम हीप का बिल्ड फ़्लॉइड के रैखिक-समय हीप बिल्ड एल्गोरिदम के अनुकूलन द्वारा पूर्ण किया जाता है, जो नीचे से ऊपर की ओर बढ़ता है।<ref name=":1" /> एक विशिष्ट फ़्लॉइड का बिल्ड-हीप एल्गोरिदम<ref>{{Cite journal|last=K. Paparrizos|first=Ioannis|year=2011|title=फ्लोयड के ढेर निर्माण एल्गोरिदम के लिए तुलनाओं की सबसे खराब स्थिति की संख्या पर एक सख्त बंधन|arxiv=1012.0956|bibcode=2010arXiv1012.0956P}}</ref> इस प्रकार है:
मिन-मैक्स हीप का बिल्ड फ़्लॉइड के रैखिक-समय हीप बिल्ड एल्गोरिदम के अनुकूलन द्वारा पूर्ण किया जाता है, जो नीचे से ऊपर की ओर बढ़ता है।<ref name=":1" /> एक विशिष्ट फ़्लॉइड का बिल्ड-हीप एल्गोरिदम<ref>{{Cite journal|last=K. Paparrizos|first=Ioannis|year=2011|title=फ्लोयड के ढेर निर्माण एल्गोरिदम के लिए तुलनाओं की सबसे खराब स्थिति की संख्या पर एक सख्त बंधन|arxiv=1012.0956|bibcode=2010arXiv1012.0956P}}</ref> इस प्रकार निम्नलिखित है:


  '''function FLOYD-BUILD-HEAP'''(''h''):
  '''function FLOYD-BUILD-HEAP'''(''h''):
Line 45: Line 45:
         '''push-down'''(''h'', ''i'')
         '''push-down'''(''h'', ''i'')
     '''return''' h
     '''return''' h
इस फलन में, ''h'' प्रारंभिक सरणी है, जिसके अवयवों को न्यूनतम-अधिकतम हीप गुण के अनुसार क्रमबद्ध नहीं किया जा सकता है। न्यूनतम-अधिकतम हीप के <code>push-down</code> ऑपरेशन (जिसे कभी-कभी हेपिफाई भी कहा जाता है) को आगे समझाया गया है।
इस फलन में, ''h'' प्रारंभिक सरणी है, जिसके अवयवों को मिन-मैक्स हीप गुण के अनुसार क्रमबद्ध नहीं किया जा सकता है। मिन-मैक्स हीप के <code>push-down</code> ऑपरेशन (जिसे कभी-कभी हेपिफाई भी कहा जाता है) को आगे पूर्ण रूप से समझाया गया है।


==== पुश डाउन ====
==== पुश डाउन ====
Line 59: Line 59:
     '''endif'''
     '''endif'''


==== पुश डाउन न्यूनतम ====
==== पुश डाउन मिन ====


  '''function PUSH-DOWN-MIN'''(''h'', ''i''):
  '''function PUSH-DOWN-MIN'''(''h'', ''i''):
Line 81: Line 81:
     '''endif'''
     '''endif'''


==== अधिकतम पुश-डाउन ====
==== मैक्स पुश-डाउन ====


<code>push-down-max</code> के लिए एल्गोरिदम पुश-डाउन-मिन के समान है, परन्तु सभी तुलना ऑपरेटर उत्क्रमित हो गए हैं।
<code>push-down-max</code> के लिए एल्गोरिदम पुश-डाउन-मिन के समान है, परन्तु सभी तुलना ऑपरेटर उत्क्रमित हो गए हैं।
Line 106: Line 106:


==== पुनरावृत्त रूप ====
==== पुनरावृत्त रूप ====
चूंकि <code>push-down-min</code> और <code>push-down-max</code> पुनरावर्ती कॉल पश्च की स्थिति में हैं, इन प्रकार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:
चूंकि <code>push-down-min</code> और <code>push-down-max</code> पुनरावर्ती कॉल पश्च की स्थिति में हैं, इस प्रकार से इन प्रकार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:
  '''function PUSH-DOWN-ITER'''(''h'', ''m''):
  '''function PUSH-DOWN-ITER'''(''h'', ''m''):
     '''while''' ''m'' has children '''then:'''
     '''while''' ''m'' has children '''then:'''
Line 144: Line 144:


=== इन्सर्टेसन ===
=== इन्सर्टेसन ===
न्यूनतम-अधिकतम हीप में अवयव जोड़ने के लिए निम्नलिखित निष्पादन करें:
इस प्रकार से मिन-मैक्स हीप में अवयव जोड़ने के लिए निम्नलिखित निष्पादन करें:


# न्यूनतम-अधिकतम हीप का प्रतिनिधित्व करने वाली सरणी के (अंत में) आवश्यक कुंजी जोड़ें। इससे संभवतः न्यूनतम-अधिकतम हीप गुण टूट जाएंगे, इसलिए हमें हीप को समायोजित करने की आवश्यकता है।
# मिन-मैक्स हीप का प्रतिनिधित्व करने वाली सरणी के (अंत में) आवश्यक कुंजी जोड़ें। इससे संभवतः मिन-मैक्स हीप गुण टूट जाएंगे, इसलिए हमें हीप को समायोजित करने की आवश्यकता है।
# नवीन कुंजी की उसके मूल कुंजी से तुलना करें:
# नवीन कुंजी की उसके मूल कुंजी से तुलना करें:
## यदि यह मूल से कम (अधिक) पाया जाता है, तो यह निश्चित रूप से अधिकतम (न्यूनतम) स्तरों पर अन्य सभी नोड की तुलना में कम (अधिक) है जो हीप की रूट के मार्ग पर हैं। अब, मात्र न्यूनतम (अधिकतम) स्तरों पर नोड की जाँच करें।
## यदि यह मूल से कम (अधिक) पाया जाता है, तो यह निश्चित रूप से मैक्स (मिन) स्तरों पर अन्य सभी नोड की तुलना में कम (अधिक) है जो हीप की रूट के मार्ग पर हैं। अतः अब, मात्र मिन (मैक्स) स्तरों पर नोड की जाँच करें।
## नवीन नोड से रूट तक का पथ (मात्र न्यूनतम (अधिकतम) स्तरों पर विचार करते हुए) अवरोही (आरोही) क्रम में होना चाहिए जैसा कि इन्सर्टेसन से पहले था। इसलिए, हमें इस क्रम में नवीन नोड का बाइनरी इन्सर्टेसन करने की आवश्यकता है। तकनीकी रूप से नवीन नोड को उसके पैरेंट के साथ स्वैप करना सरल है जबकि पैरेंट बड़ा (कम) है।
## नवीन नोड से रूट तक का पथ (मात्र मिन (मैक्स) स्तरों पर विचार करते हुए) अवरोही (आरोही) क्रम में होना चाहिए जैसा कि इन्सर्टेसन से पहले था। इसलिए, हमें इस क्रम में नवीन नोड का बाइनरी इन्सर्टेसन करने की आवश्यकता है। तकनीकी रूप से नवीन नोड को उसके पैरेंट के साथ स्वैप करना सरल है जबकि पैरेंट बड़ा (कम) है।


यह प्रक्रिया नवीन संलग्न कुंजी के सूचकांक पर नीचे वर्णित <code>push-up</code> एल्गोरिदम को कॉल करके कार्यान्वित की जाती है।
इस प्रकार से यह प्रक्रिया नवीन संलग्न कुंजी के सूचकांक पर नीचे वर्णित <code>push-up</code> एल्गोरिदम को कॉल करके कार्यान्वित की जाती है।


=== पुश अप ===
=== पुश अप ===
Line 180: Line 180:
     '''endif'''
     '''endif'''


==== पुश अप न्यूनतम ====
==== पुश अप मिन ====


  '''function PUSH-UP-MIN'''(''h'', ''i''):
  '''function PUSH-UP-MIN'''(''h'', ''i''):
Line 190: Line 190:
     '''endif'''
     '''endif'''


==== अधिकतम पुश अप ====
==== मैक्स पुश अप ====
<code>push-down</code> ऑपरेशन के जैसे, <code>push-up-max</code> <code>push-up-min</code> के समान है, परन्तु तुलनात्मक ऑपरेटरों के विपरीत:
<code>push-down</code> ऑपरेशन के जैसे, <code>push-up-max</code> <code>push-up-min</code> के समान है, परन्तु तुलनात्मक ऑपरेटरों के विपरीत:
  फलन पुश-अप-अधिकतम(''एच'', ''आई''):
  '''function PUSH-UP-MAX'''(''h'', ''i''):
     यदि ''i'' के दादा-दादी हैं और ''h[i] > h[दादा-दादी(i)]'' तो:
 
         ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें
     '''if''' ''i'' has a grandparent '''and''' ''h[i] > h[grandparent(i)]'' '''then:'''
         पुश-अप-अधिकतम(''एच, दादा-दादी(i)'')
         swap ''h[i]'' and ''h[grandparent(i)]''
     यदि अंत
 
         '''PUSH-UP-MAX'''(''h, grandparent(i)'')
     '''endif'''


==== पुनरावृत्त रूप ====
==== पुनरावृत्त रूप ====
जैसा कि पुनरावर्ती कॉल करता है <code>push-up-min</code> और <code>push-up-max</code> पूंछ की स्थिति में हैं, इन कार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में भी परिवर्तित किया जा सकता है:
चूंकि <code>push-up-min</code> और <code>push-up-max</code> के लिए पुनरावर्ती कॉल पश्च की स्थिति में पूर्ण रूप से हैं, इसलिए इन प्रकार्यों को भी निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:
  फलन पुश-अप-न्यूनतम-इटर(''एच'', ''आई''):
  '''function PUSH-UP-MIN-ITER'''(''h'', ''i''):
     जबकि ''i'' के दादा-दादी हैं और ''h[i] < h[grandparent(i)]'' तो:
 
         ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें
     '''while''' ''i'' has a grandparent '''and''' ''h[i] < h[grandparent(i)]'' '''then:'''
         ''मैं'' := ''दादा-दादी(i)''
         swap ''h[i]'' and ''h[grandparent(i)]''
     अंत तक
 
         ''i'' := ''grandparent(i)''
     '''endwhile'''


==== उदाहरण ====
==== उदाहरण ====
यहां न्यूनतम-अधिकतम हीप में अवयव डालने का उदाहरण दिया गया है।
इस प्रकार से यहां मिन-मैक्स हीप में अवयव डालने का उदाहरण दिया गया है।


मान लें कि हमारे पास निम्नलिखित न्यूनतम-अधिकतम हीप है और हम मान 6 के साथ नवीन नोड सम्मिलित करना चाहते हैं।
अतः मान लें कि हमारे निकट निम्नलिखित मिन-मैक्स हीप है और हम मान 6 के साथ नवीन नोड को पूर्ण रूप से सम्मिलित करना चाहते हैं।


::[[File:Min-max heap.jpg|400px|न्यूनतम-अधिकतम ढेर का उदाहरण]]प्रारंभ में, नोड 6 को नोड 11 के दाएं बच्चे के रूप में डाला गया है। 6, 11 से कम है, इसलिए यह अधिकतम स्तर (41) पर सभी नोड से कम है, और हमें मात्र न्यूनतम स्तर (8 और 11) की जांच करने की आवश्यकता है )। हमें नोड 6 और 11 को स्वैप करना चाहिए और फिर 6 और 8 को स्वैप करना चाहिए। तो, 6 को हीप की मूल स्थिति में ले जाया जाता है, पूर्व रूट 8 को 11 की जगह लेने के लिए नीचे ले जाया जाता है, और 11 8 का सही बच्चा बन जाता है।
::[[File:Min-max heap.jpg|400px|न्यूनतम-अधिकतम ढेर का उदाहरण]]
::प्रारंभ में, नोड 6 को नोड 11 के दाएं बच्चे के रूप में डाला गया है। इस प्रकार से 6, 11 से कम है, इसलिए यह मैक्स स्तर (41) पर सभी नोड से कम है, और हमें मात्र मिन स्तर (8 और 11) की फाइंड करने की आवश्यकता है)। हमें नोड 6 और 11 को स्वैप करना चाहिए और फिर 6 और 8 को स्वैप करना चाहिए। तो, 6 को हीप की मूल स्थिति में ले जाया जाता है, पूर्व रूट 8 को 11 का स्थान लेने के लिए नीचे ले जाया जाता है, और 11 8 का दायाँ चिल्ड्रेन बन जाता है।


6 के बजाय नवीन नोड 81 जोड़ने पर विचार करें। प्रारंभ में, नोड को नोड 11 के दाहिने बच्चे के रूप में डाला जाता है। 81, 11 से बड़ा है, इसलिए यह किसी भी न्यूनतम स्तर (8 और 11) पर किसी भी नोड से बड़ा है। अब, हमें मात्र अधिकतम स्तर (41) पर नोड की जांच करने और स्वैप करने की आवश्यकता है।
इस प्रकार से 6 के अतिरिक्त नवीन नोड 81 जोड़ने पर विचार करें। प्रारंभ में, नोड को नोड 11 के दाहिने बच्चे के रूप में डाला जाता है। 81, 11 से बड़ा है, इसलिए यह किसी भी मिन स्तर (8 और 11) पर किसी भी नोड से बड़ा है। अब, हमें मात्र मैक्स स्तर (41) पर नोड की फाइंड करने और स्वैप करने की आवश्यकता है।


=== न्यूनतम खोजें ===
=== फाइंड मिन ===


न्यूनतम-अधिकतम हीप का न्यूनतम नोड (या डुप्लिकेट कुंजियों के मामले में न्यूनतम नोड) हमेशा रूट पर स्थित होता है। न्यूनतम खोजें इस प्रकार तुच्छ स्थिर समय ऑपरेशन है जो बस रूटें लौटाता है।
अतः मिन-मैक्स हीप का मिन नोड (या डुप्लिकेट कुंजियों की स्थिति में मिन नोड) सदैव रूट पर स्थित होता है। इस प्रकार से मिन फाइंड इस प्रकार तुच्छ स्थिर समय ऑपरेशन है जो मात्र रूटें लौटाता है।


=== अधिकतम ज्ञात करें ===
=== फाइंड मैक्स ===


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


=== न्यूनतम हटाएं ===
=== रिमूव मिन ===
न्यूनतम को हटाना मनमाना नोड को हटाने का विशेष मामला है जिसका सरणी में सूचकांक ज्ञात है। इस स्थिति में, सरणी का अंतिम अवयव हटा दिया जाता है (सरणी की लंबाई कम कर दी जाती है) और सरणी के शीर्ष पर रूट को बदलने के लिए उपयोग किया जाता है। <code>push-down</code> फिर हीप प्रॉपर्टी को पुनर्स्थापित करने के लिए रूट इंडेक्स पर कॉल किया जाता है <math>O(\log_2(n))</math>समय।
इस प्रकार से मिन को हटाना यादृच्छिक नोड को रिमूव की विशेष स्थिति है जिसका सरणी में सूचकांक ज्ञात है। इस स्थिति में, सरणी का अंतिम अवयव हटा दिया जाता है (सरणी की लंबाई कम कर दी जाती है) और सरणी के शीर्ष पर रूट को बदलने के लिए उपयोग किया जाता है। अतः <math>O(\log_2(n))</math>समय में हीप गुण को पुनर्स्थापित करने के लिए रूट सूचकांक पर <code>push-down</code> को कॉल किया जाता है।


=== अधिकतम हटाएं ===
=== रिमूव मैक्स ===
अधिकतम को हटाना फिर से ज्ञात सूचकांक के साथ मनमाना नोड को हटाने का विशेष मामला है। जैसा कि अधिकतम खोजें ऑपरेशन में, रूट के अधिकतम बच्चे की पहचान करने के लिए एकल तुलना की आवश्यकता होती है, जिसके बाद इसे सरणी के अंतिम अवयव से बदल दिया जाता है और <code>push-down</code> फिर हीप गुण को पुनर्स्थापित करने के लिए प्रतिस्थापित अधिकतम के सूचकांक पर कॉल किया जाता है।
अतः इस प्रकार से रिमूव मैक्स फिर से ज्ञात सूचकांक के साथ यादृच्छिक नोड को रिमूव की विशेष स्थिति है। जैसा कि मैक्स फाइंड ऑपरेशन में, रूट के मैक्स बच्चे की पहचान करने के लिए एकल तुलना की आवश्यकता होती है, जिसके बाद इसे सरणी के अंतिम अवयव के साथ बदल दिया जाता है और फिर हीप गुण को पुनर्स्थापित करने के लिए प्रतिस्थापित मैक्स के सूचकांक पर <code>push-down</code> को कॉल किया जाता है।


== एक्सटेंशन ==
== एक्सटेंशन ==


न्यूनतम-अधिकतम-माध्यिका हीप न्यूनतम-अधिकतम हीप का प्रकार है, जो संरचना पर मूल प्रकाशन में सुझाया गया है, जो [[आदेश आँकड़ा वृक्ष|आदेश आँकड़ा ट्री]] के ऑपरेशन का समर्थन करता है।
इस प्रकार से मिन-मैक्स-माध्यिका हीप मिन-मैक्स हीप का एक ऐसा प्रकार है, जो संरचना पर मूल प्रकाशन में सुझाया गया है, जो [[आदेश आँकड़ा वृक्ष|क्रम डेटा ट्री]] के ऑपरेशन का सपोर्ट करता है।


== संदर्भ ==
== संदर्भ ==
{{Reflist}}
{{Reflist}}
*  
*
[[Category: प्राथमिकता कतारें]] [[Category: ढेर (डेटा संरचनाएं)]]
 
 


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:CS1 errors]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ढेर (डेटा संरचनाएं)]]
[[Category:प्राथमिकता कतारें]]

Latest revision as of 15:18, 31 July 2023

Min-max heap
Typebinary tree/heap
Invented1986
Time complexity in big O notation
Algorithm Average Worst case
Insert O(log n) O(log n)
Delete O(log n) [1] O(log n)

कंप्यूटर विज्ञान में, मिन-मैक्स हीप पूर्ण बाइनरी ट्री डेटा संरचना है जो मिन-हीप और मैक्स-हीप दोनों की उपयोगिता को जोड़ती है, अर्थात, यह मिन और मैक्स दोनों अवयवों की निरंतर समय पुनर्प्राप्ति और लॉगरिदमिक समय निष्कासन प्रदान करती है।[2] अतः यह डबल-एंड प्रायोरिटी क्यू को लागू करने के लिए मिन-मैक्स हीप को बहुत ही उपयोगी डेटा संरचना बनाता है। बाइनरी मिन-हीप और मैक्स-हीप के जैसे, मिन-मैक्स हीप लॉगरिदमिक इन्सर्टेसन और डेलेसन का समर्थन करते हैं और रैखिक समय में बनाए जा सकते हैं।[3] मिन-मैक्स हीप को प्रायः सरणी में इम्प्लिसिटी रूप से दर्शाया जाता है;[4] इसलिए इसे इम्प्लिसिटी डेटा संरचना के रूप में जाना जाता है।

इस प्रकार से मिन-मैक्स हीप गुण है: ट्री में सम स्तर पर प्रत्येक नोड उसके सभी वंशजों से कम है, जबकि ट्री में विषम स्तर पर प्रत्येक नोड उसके सभी वंशजों से बड़ा है।[4]

अतः संरचना को अन्य क्रम-सांख्यिकी ऑपरेशन को कुशलतापूर्वक समर्थन देने के लिए भी सामान्यीकृत किया जा सकता है, जैसे कि find-median, delete-median,[2]find(k) (संरचना में kवां सबसे छोटा मान निर्धारित करें) और ऑपरेशन delete(k) (संरचना में kवां सबसे छोटा मान हटाएं), k के किसी निश्चित मान (या मानों के समूह) के लिए। इन अंतिम दो ऑपरेशनों को क्रमशः स्थिर और लघुगणकीय समय में कार्यान्वित किया जा सकता है। इस प्रकार से मिन-मैक्स क्रमण की धारणा को मैक्स या मिन-क्रमण के आधार पर अन्य संरचनाओं तक बढ़ाया जा सकता है, जैसे लेफ्टिस ट्री, डेटा संरचनाओं का नवीन (और अधिक शक्तिशाली) वर्ग उत्पन्न करते हैं।[4] अतः बाहरी क्विकसॉर्ट लागू करते समय मिन-मैक्स हीप भी पूर्ण रूप से उपयोगी हो सकता है।[5]

विवरण

  • मिन-मैक्स हीप पूर्ण बाइनरी ट्री है जिसमें वैकल्पिक मिन (या सम) और मैक्स (या विषम) स्तर होते हैं। इस प्रकार से सम स्तर उदाहरण के लिए 0, 2, 4, आदि हैं, और विषम स्तर क्रमशः 1, 3, 5, आदि हैं। हम अगले बिंदुओं में मानते हैं कि मूल अवयव पहले स्तर पर है, अर्थात 0।
मिन-मैक्स हीप का उदाहरण
  • मिन-मैक्स हीप में प्रत्येक नोड में डेटा सदस्य (सामान्यतः कुंजी कहा जाता है) होता है जिसका मान मिन-मैक्स हीप में नोड के क्रम को निर्धारित करने के लिए पूर्ण रूप से उपयोग किया जाता है।
  • मूल अवयव मिन-मैक्स हीप में सबसे छोटा अवयव है।
  • दूसरे स्तर के दो अवयवों में से एक है, जो मैक्स (या विषम) स्तर है, मिन-मैक्स हीप में सबसे बड़ा अवयव है।
  • मान लीजिए मिन-मैक्स हीप में कोई नोड है।
    • यदि मिन (या सम) स्तर पर है, तो रूट के साथ उपट्री में सभी कुंजियों के बीच मिन कुंजी है।
    • यदि मैक्स (या विषम) स्तर पर है, तो रूट के साथ उपट्री में सभी कुंजियों के बीच मैक्स कुंजी है।
  • मिन (मैक्स) स्तर पर नोड को मिन (मैक्स) नोड कहा जाता है।

इस प्रकार से मैक्स-मिन हीप को समान रूप से परिभाषित किया गया है; ऐसे हीप में, मैक्स मान रूट पर संग्रहीत होता है, और सबसे छोटा मान रूट के बच्चों में से पर संग्रहीत होता है।[4]

ऑपरेशन

इस प्रकार से निम्नलिखित ऑपरेशनों में हम मानते हैं कि मिन-मैक्स हीप को सरणी A[1।।N] में दर्शाया गया है; सरणी में स्थान हीप में स्तर पर स्थित नोड के अनुरूप होगा।

बिल्ड

मिन-मैक्स हीप का बिल्ड फ़्लॉइड के रैखिक-समय हीप बिल्ड एल्गोरिदम के अनुकूलन द्वारा पूर्ण किया जाता है, जो नीचे से ऊपर की ओर बढ़ता है।[4] एक विशिष्ट फ़्लॉइड का बिल्ड-हीप एल्गोरिदम[6] इस प्रकार निम्नलिखित है:

function FLOYD-BUILD-HEAP(h):
    for each index i from  down to 1 do:
        push-down(h, i)
    return h

इस फलन में, h प्रारंभिक सरणी है, जिसके अवयवों को मिन-मैक्स हीप गुण के अनुसार क्रमबद्ध नहीं किया जा सकता है। मिन-मैक्स हीप के push-down ऑपरेशन (जिसे कभी-कभी हेपिफाई भी कहा जाता है) को आगे पूर्ण रूप से समझाया गया है।

पुश डाउन

push-down एल्गोरिदम (या trickle-down जैसा कि इसे कहा जाता है [4]) इस प्रकार है:

function PUSH-DOWN(h, i):
    if i is on a min level then:
    PUSH-DOWN-MIN(h, i)
    else:
        PUSH-DOWN-MAX(h, i)
    endif

पुश डाउन मिन

function PUSH-DOWN-MIN(h, i):
    if i has children then:
        m := index of the smallest child or grandchild of i
        if m is a grandchild of i then:
            if h[m] < h[i] then:
                swap h[m] and h[i]
                if h[m] > h[parent(m)] then:
                    swap h[m] and h[parent(m)]
                endif
                PUSH-DOWN(h, m)
            endif
        else if h[m] < h[i] then:
            swap h[m] and h[i]
        endif 
    endif

मैक्स पुश-डाउन

push-down-max के लिए एल्गोरिदम पुश-डाउन-मिन के समान है, परन्तु सभी तुलना ऑपरेटर उत्क्रमित हो गए हैं।

function PUSH-DOWN-MAX(h, i):
    if i has children then:
        m := index of the largest child or grandchild of i
        if m is a grandchild of i then:
            if h[m] > h[i] then:
                swap h[m] and h[i]
                if h[m] < h[parent(m)] then:
                    swap h[m] and h[parent(m)]
                endif
                PUSH-DOWN(h, m)
            endif
        else if h[m] > h[i] then:
            swap h[m] and h[i]
        endif 
    endif

पुनरावृत्त रूप

चूंकि push-down-min और push-down-max पुनरावर्ती कॉल पश्च की स्थिति में हैं, इस प्रकार से इन प्रकार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:

function PUSH-DOWN-ITER(h, m):
    while m has children then:
        i := m
        if i is on a min level then:
            m := index of the smallest child or grandchild of i
            if h[m] < h[i] then:
                swap h[m] and h[i]
                if m is a grandchild of i then:
                    if h[m] > h[parent(m)] then:
                        swap h[m] and h[parent(m)]
                    endif
                else
                    break
                endif
            else
                break 
            endif
        else:
            m := index of the largest child or grandchild of i
            if h[m] > h[i] then:
                swap h[m] and h[i]
                if m is a grandchild of i then:
                    if h[m] < h[parent(m)] then:
                        swap h[m] and h[parent(m)]
                    endif
                else
                    break
                endif
            else
                break 
            endif
        endif
    endwhile

इन्सर्टेसन

इस प्रकार से मिन-मैक्स हीप में अवयव जोड़ने के लिए निम्नलिखित निष्पादन करें:

  1. मिन-मैक्स हीप का प्रतिनिधित्व करने वाली सरणी के (अंत में) आवश्यक कुंजी जोड़ें। इससे संभवतः मिन-मैक्स हीप गुण टूट जाएंगे, इसलिए हमें हीप को समायोजित करने की आवश्यकता है।
  2. नवीन कुंजी की उसके मूल कुंजी से तुलना करें:
    1. यदि यह मूल से कम (अधिक) पाया जाता है, तो यह निश्चित रूप से मैक्स (मिन) स्तरों पर अन्य सभी नोड की तुलना में कम (अधिक) है जो हीप की रूट के मार्ग पर हैं। अतः अब, मात्र मिन (मैक्स) स्तरों पर नोड की जाँच करें।
    2. नवीन नोड से रूट तक का पथ (मात्र मिन (मैक्स) स्तरों पर विचार करते हुए) अवरोही (आरोही) क्रम में होना चाहिए जैसा कि इन्सर्टेसन से पहले था। इसलिए, हमें इस क्रम में नवीन नोड का बाइनरी इन्सर्टेसन करने की आवश्यकता है। तकनीकी रूप से नवीन नोड को उसके पैरेंट के साथ स्वैप करना सरल है जबकि पैरेंट बड़ा (कम) है।

इस प्रकार से यह प्रक्रिया नवीन संलग्न कुंजी के सूचकांक पर नीचे वर्णित push-up एल्गोरिदम को कॉल करके कार्यान्वित की जाती है।

पुश अप

push-up एल्गोरिथ्म (या bubble-up जैसा कि इसे कहा जाता है[7]) इस प्रकार है:

function PUSH-UP(h, i):
    if i is not the root then:
        if i is on a min level then:
            if h[i] > h[parent(i)] then:
                swap h[i] and h[parent(i)]
                PUSH-UP-MAX(h, parent(i))
            else:
                PUSH-UP-MIN(h, i)
            endif
        else:
            if h[i] < h[parent(i)] then:
                swap h[i] and h[parent(i)]
                PUSH-UP-MIN(h, parent(i))
            else:
                PUSH-UP-MAX(h, i)
            endif
        endif
    endif

पुश अप मिन

function PUSH-UP-MIN(h, i):
    if i has a grandparent and h[i] < h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        PUSH-UP-MIN(h, grandparent(i))
    endif

मैक्स पुश अप

push-down ऑपरेशन के जैसे, push-up-max push-up-min के समान है, परन्तु तुलनात्मक ऑपरेटरों के विपरीत:

function PUSH-UP-MAX(h, i):
    if i has a grandparent and h[i] > h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        PUSH-UP-MAX(h, grandparent(i))
    endif

पुनरावृत्त रूप

चूंकि push-up-min और push-up-max के लिए पुनरावर्ती कॉल पश्च की स्थिति में पूर्ण रूप से हैं, इसलिए इन प्रकार्यों को भी निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:

function PUSH-UP-MIN-ITER(h, i):
    while i has a grandparent and h[i] < h[grandparent(i)] then:
        swap h[i] and h[grandparent(i)]
        i := grandparent(i)
    endwhile

उदाहरण

इस प्रकार से यहां मिन-मैक्स हीप में अवयव डालने का उदाहरण दिया गया है।

अतः मान लें कि हमारे निकट निम्नलिखित मिन-मैक्स हीप है और हम मान 6 के साथ नवीन नोड को पूर्ण रूप से सम्मिलित करना चाहते हैं।

न्यूनतम-अधिकतम ढेर का उदाहरण
प्रारंभ में, नोड 6 को नोड 11 के दाएं बच्चे के रूप में डाला गया है। इस प्रकार से 6, 11 से कम है, इसलिए यह मैक्स स्तर (41) पर सभी नोड से कम है, और हमें मात्र मिन स्तर (8 और 11) की फाइंड करने की आवश्यकता है)। हमें नोड 6 और 11 को स्वैप करना चाहिए और फिर 6 और 8 को स्वैप करना चाहिए। तो, 6 को हीप की मूल स्थिति में ले जाया जाता है, पूर्व रूट 8 को 11 का स्थान लेने के लिए नीचे ले जाया जाता है, और 11 8 का दायाँ चिल्ड्रेन बन जाता है।

इस प्रकार से 6 के अतिरिक्त नवीन नोड 81 जोड़ने पर विचार करें। प्रारंभ में, नोड को नोड 11 के दाहिने बच्चे के रूप में डाला जाता है। 81, 11 से बड़ा है, इसलिए यह किसी भी मिन स्तर (8 और 11) पर किसी भी नोड से बड़ा है। अब, हमें मात्र मैक्स स्तर (41) पर नोड की फाइंड करने और स्वैप करने की आवश्यकता है।

फाइंड मिन

अतः मिन-मैक्स हीप का मिन नोड (या डुप्लिकेट कुंजियों की स्थिति में मिन नोड) सदैव रूट पर स्थित होता है। इस प्रकार से मिन फाइंड इस प्रकार तुच्छ स्थिर समय ऑपरेशन है जो मात्र रूटें लौटाता है।

फाइंड मैक्स

अतः मिन-मैक्स हीप का मैक्स नोड (या डुप्लिकेट कुंजियों की स्थिति में मैक्स नोड) जिसमें से अधिक नोड होते हैं, सदैव पहले मैक्स स्तर पर स्थित होता है - अर्थात, रूट के तत्काल बच्चों में से के रूप में है। मैक्स फाइंड इस प्रकार मैक्स तुलना की आवश्यकता होती है, यह निर्धारित करने के लिए कि रूट के दो बच्चों में से कौन सा बड़ा है, और इस प्रकार यह निरंतर समय ऑपरेशन भी है। यदि मिन-मैक्स हीप में नोड है तो वह नोड मैक्स नोड है।

रिमूव मिन

इस प्रकार से मिन को हटाना यादृच्छिक नोड को रिमूव की विशेष स्थिति है जिसका सरणी में सूचकांक ज्ञात है। इस स्थिति में, सरणी का अंतिम अवयव हटा दिया जाता है (सरणी की लंबाई कम कर दी जाती है) और सरणी के शीर्ष पर रूट को बदलने के लिए उपयोग किया जाता है। अतः समय में हीप गुण को पुनर्स्थापित करने के लिए रूट सूचकांक पर push-down को कॉल किया जाता है।

रिमूव मैक्स

अतः इस प्रकार से रिमूव मैक्स फिर से ज्ञात सूचकांक के साथ यादृच्छिक नोड को रिमूव की विशेष स्थिति है। जैसा कि मैक्स फाइंड ऑपरेशन में, रूट के मैक्स बच्चे की पहचान करने के लिए एकल तुलना की आवश्यकता होती है, जिसके बाद इसे सरणी के अंतिम अवयव के साथ बदल दिया जाता है और फिर हीप गुण को पुनर्स्थापित करने के लिए प्रतिस्थापित मैक्स के सूचकांक पर push-down को कॉल किया जाता है।

एक्सटेंशन

इस प्रकार से मिन-मैक्स-माध्यिका हीप मिन-मैक्स हीप का एक ऐसा प्रकार है, जो संरचना पर मूल प्रकाशन में सुझाया गया है, जो क्रम डेटा ट्री के ऑपरेशन का सपोर्ट करता है।

संदर्भ

  1. Mischel. "Jim". Stack Overflow. Retrieved 8 September 2016.
  2. 2.0 2.1 ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें" (PDF). Communications of the ACM (in English). 29 (10): 996–1000. doi:10.1145/6617.6621. S2CID 3090797.
  3. ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें" (PDF). Communications of the ACM (in English). 29 (10): 996–1000. doi:10.1145/6617.6621. S2CID 3090797.
  4. 4.0 4.1 4.2 4.3 4.4 4.5 ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें" (PDF). Communications of the ACM (in English). 29 (10): 996–1000. doi:10.1145/6617.6621. S2CID 3090797.
  5. Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). Handbook of Algorithms and Data Structures: In Pascal and C. ISBN 0201416077.
  6. K. Paparrizos, Ioannis (2011). "फ्लोयड के ढेर निर्माण एल्गोरिदम के लिए तुलनाओं की सबसे खराब स्थिति की संख्या पर एक सख्त बंधन". arXiv:1012.0956. Bibcode:2010arXiv1012.0956P. {{cite journal}}: Cite journal requires |journal= (help)
  7. ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "न्यूनतम-अधिकतम ढेर और सामान्यीकृत प्राथमिकता कतारें" (PDF). Communications of the ACM (in English). 29 (10): 996–1000. doi:10.1145/6617.6621. S2CID 3090797.