मिन-मैक्स हीप: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| 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=":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> | ||
== विवरण == | == विवरण == | ||
* | *न्यूनतम-अधिकतम हीप पूर्ण बाइनरी ट्री है जिसमें वैकल्पिक न्यूनतम (या सम) और अधिकतम (या विषम) स्तर होते हैं। सम स्तर उदाहरण के लिए 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.key</math> के साथ उपट्री में सभी कुंजियों के बीच <math>x</math> न्यूनतम कुंजी है। | |||
** यदि <math>x</math> अधिकतम (या विषम) स्तर पर है, तो रूट <math>x.key</math> के साथ उपट्री में सभी कुंजियों के बीच <math>x</math> अधिकतम कुंजी है। | |||
* न्यूनतम (अधिकतम) स्तर पर नोड को न्यूनतम (अधिकतम) नोड कहा जाता है। | * न्यूनतम (अधिकतम) स्तर पर नोड को न्यूनतम (अधिकतम) नोड कहा जाता है। | ||
अधिकतम-न्यूनतम | अधिकतम-न्यूनतम हीप को समान रूप से परिभाषित किया गया है; ऐसे हीप में, अधिकतम मान रूट पर संग्रहीत होता है, और सबसे छोटा मान रूट के बच्चों में से पर संग्रहीत होता है।<ref name=":1" /> | ||
== | ==ऑपरेशन == | ||
निम्नलिखित ऑपरेशनों में हम मानते हैं कि न्यूनतम-अधिकतम हीप को सरणी <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> इस प्रकार है: | ||
'''function FLOYD-BUILD-HEAP'''(''h''): | |||
'''for''' each index ''i'' from <math>\lfloor length(h) / 2 \rfloor</math> '''down to''' 1 '''do:''' | |||
इस | '''push-down'''(''h'', ''i'') | ||
'''return''' h | |||
इस फलन में, ''h'' प्रारंभिक सरणी है, जिसके अवयवों को न्यूनतम-अधिकतम हीप गुण के अनुसार क्रमबद्ध नहीं किया जा सकता है। <code>push-down</code> ई> न्यूनतम-अधिकतम हीप के ऑपरेशन (जिसे कभी-कभी हेपिफाई भी कहा जाता है) को आगे समझाया गया है। | |||
=== नीचे दबाएं === <code>push-down</code> ई> एल्गोरिदम (या <code>trickle-down</code> जैसा कि इसमें कहा जाता है <ref name=":1" />) इस प्रकार है: | === नीचे दबाएं === <code>push-down</code> ई> एल्गोरिदम (या <code>trickle-down</code> जैसा कि इसमें कहा जाता है <ref name=":1" />) इस प्रकार है: | ||
फलन पुश-डाउन(''एच'', ''आई''): | |||
यदि ''i'' न्यूनतम स्तर पर है तो: | यदि ''i'' न्यूनतम स्तर पर है तो: | ||
पुश-डाउन-मिन(''एच'', ''आई'') | पुश-डाउन-मिन(''एच'', ''आई'') | ||
अन्य: | अन्य: | ||
पुश-डाउन- | पुश-डाउन-अधिकतम(''एच'', ''आई'') | ||
यदि अंत | |||
==== पुश डाउन न्यूनतम ==== | ==== पुश डाउन न्यूनतम ==== | ||
फलन पुश-डाउन-मिन(''एच'', ''आई''): | |||
यदि ''मेरे'' के बच्चे हैं तो: | यदि ''मेरे'' के बच्चे हैं तो: | ||
''m'' := ''i'' के सबसे छोटे बच्चे या पोते का सूचकांक | ''m'' := ''i'' के सबसे छोटे बच्चे या पोते का सूचकांक | ||
| Line 62: | Line 66: | ||
यदि ''h[m]'' > ''h[parent(m)]'' तो: | यदि ''h[m]'' > ''h[parent(m)]'' तो: | ||
''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ||
यदि अंत | |||
पुश-डाउन(''एच'', ''एम'') | पुश-डाउन(''एच'', ''एम'') | ||
यदि अंत | |||
अन्यथा यदि ''h[m]'' < ''h[i]'' तो: | अन्यथा यदि ''h[m]'' < ''h[i]'' तो: | ||
''h[m]'' और ''h[i]'' की अदला-बदली करें | ''h[m]'' और ''h[i]'' की अदला-बदली करें | ||
यदि अंत | |||
यदि अंत | |||
==== अधिकतम नीचे पुश करें ==== | ==== अधिकतम नीचे पुश करें ==== | ||
| Line 74: | Line 78: | ||
के लिए एल्गोरिदम <code>push-down-max</code> पुश-डाउन-मिन के समान है, लेकिन सभी तुलना ऑपरेटर उलट गए हैं। | के लिए एल्गोरिदम <code>push-down-max</code> पुश-डाउन-मिन के समान है, लेकिन सभी तुलना ऑपरेटर उलट गए हैं। | ||
फलन पुश-डाउन-अधिकतम(''एच'', ''आई''): | |||
यदि ''मेरे'' के बच्चे हैं तो: | यदि ''मेरे'' के बच्चे हैं तो: | ||
''m'' := ''i'' के सबसे बड़े बच्चे या पोते का सूचकांक | ''m'' := ''i'' के सबसे बड़े बच्चे या पोते का सूचकांक | ||
| Line 82: | Line 86: | ||
यदि ''h[m]'' < ''h[parent(m)]'' तो: | यदि ''h[m]'' < ''h[parent(m)]'' तो: | ||
''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ||
यदि अंत | |||
पुश-डाउन(''एच'', ''एम'') | पुश-डाउन(''एच'', ''एम'') | ||
यदि अंत | |||
अन्यथा यदि ''h[m]'' > ''h[i]'' तो: | अन्यथा यदि ''h[m]'' > ''h[i]'' तो: | ||
''h[m]'' और ''h[i]'' की अदला-बदली करें | ''h[m]'' और ''h[i]'' की अदला-बदली करें | ||
यदि अंत | |||
यदि अंत | |||
==== पुनरावृत्त प्रपत्र ==== | ==== पुनरावृत्त प्रपत्र ==== | ||
जैसे ही पुनरावर्ती कॉल आती है <code>push-down-min</code> और <code>push-down-max</code> पूंछ की स्थिति में हैं, इन कार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है: | जैसे ही पुनरावर्ती कॉल आती है <code>push-down-min</code> और <code>push-down-max</code> पूंछ की स्थिति में हैं, इन कार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है: | ||
फलन पुश-डाउन-इटर(''एच'', ''एम''): | |||
जबकि ''m'' के बच्चे हैं तो: | जबकि ''m'' के बच्चे हैं तो: | ||
''मैं := एम'' | ''मैं := एम'' | ||
| Line 102: | Line 106: | ||
यदि ''h[m]'' > ''h[parent(m)]'' तो: | यदि ''h[m]'' > ''h[parent(m)]'' तो: | ||
''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ||
यदि अंत | |||
अन्य | अन्य | ||
तोड़ना | तोड़ना | ||
यदि अंत | |||
अन्य | अन्य | ||
तोड़ना | तोड़ना | ||
यदि अंत | |||
अन्य: | अन्य: | ||
''m'' := ''i'' के सबसे बड़े बच्चे या पोते का सूचकांक | ''m'' := ''i'' के सबसे बड़े बच्चे या पोते का सूचकांक | ||
| Line 116: | Line 120: | ||
यदि ''h[m]'' < ''h[parent(m)]'' तो: | यदि ''h[m]'' < ''h[parent(m)]'' तो: | ||
''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ''h[m]'' और ''h[parent(m)]'' को स्वैप करें | ||
यदि अंत | |||
अन्य | अन्य | ||
तोड़ना | तोड़ना | ||
यदि अंत | |||
अन्य | अन्य | ||
तोड़ना | तोड़ना | ||
यदि अंत | |||
यदि अंत | |||
अंत तक | अंत तक | ||
=== निवेशन === | === निवेशन === | ||
न्यूनतम-अधिकतम | न्यूनतम-अधिकतम हीप में अवयव जोड़ने के लिए निम्नलिखित कार्य करें: | ||
# न्यूनतम-अधिकतम | # न्यूनतम-अधिकतम हीप का प्रतिनिधित्व करने वाली सरणी के (अंत में) आवश्यक कुंजी जोड़ें। इससे संभवतः न्यूनतम-अधिकतम हीप गुण टूट जाएंगे, इसलिए हमें हीप को समायोजित करने की आवश्यकता है। | ||
# नई कुंजी की उसके मूल कुंजी से तुलना करें: | # नई कुंजी की उसके मूल कुंजी से तुलना करें: | ||
## यदि यह मूल से कम (अधिक) पाया जाता है, तो यह निश्चित रूप से अधिकतम (न्यूनतम) स्तरों पर अन्य सभी नोड्स की तुलना में कम (अधिक) है जो | ## यदि यह मूल से कम (अधिक) पाया जाता है, तो यह निश्चित रूप से अधिकतम (न्यूनतम) स्तरों पर अन्य सभी नोड्स की तुलना में कम (अधिक) है जो हीप की जड़ के रास्ते पर हैं। अब, बस न्यूनतम (अधिकतम) स्तरों पर नोड्स की जाँच करें। | ||
## नए नोड से रूट तक का पथ (केवल न्यूनतम (अधिकतम) स्तरों पर विचार करते हुए) अवरोही (आरोही) क्रम में होना चाहिए जैसा कि सम्मिलन से पहले था। इसलिए, हमें इस क्रम में नए नोड का बाइनरी सम्मिलन करने की आवश्यकता है। तकनीकी रूप से नए नोड को उसके पैरेंट के साथ स्वैप करना आसान है जबकि पैरेंट बड़ा (कम) है। | ## नए नोड से रूट तक का पथ (केवल न्यूनतम (अधिकतम) स्तरों पर विचार करते हुए) अवरोही (आरोही) क्रम में होना चाहिए जैसा कि सम्मिलन से पहले था। इसलिए, हमें इस क्रम में नए नोड का बाइनरी सम्मिलन करने की आवश्यकता है। तकनीकी रूप से नए नोड को उसके पैरेंट के साथ स्वैप करना आसान है जबकि पैरेंट बड़ा (कम) है। | ||
| Line 138: | Line 142: | ||
=== पुश अप === <code>push-up</code> ई> एल्गोरिदम (या <code>bubble-up</code> जैसा कि इसमें कहा जाता है <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> | === पुश अप === <code>push-up</code> ई> एल्गोरिदम (या <code>bubble-up</code> जैसा कि इसमें कहा जाता है <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> | ||
) इस प्रकार है: | ) इस प्रकार है: | ||
फलन पुश-अप(''एच'', ''आई''): | |||
यदि ''i'' जड़ नहीं है तो: | यदि ''i'' जड़ नहीं है तो: | ||
यदि ''i'' न्यूनतम स्तर पर है तो: | यदि ''i'' न्यूनतम स्तर पर है तो: | ||
यदि ''h[i] > h[parent(i)]'' तो: | यदि ''h[i] > h[parent(i)]'' तो: | ||
''h[i]'' और ''h[parent(i)]'' को स्वैप करें | ''h[i]'' और ''h[parent(i)]'' को स्वैप करें | ||
पुश-अप- | पुश-अप-अधिकतम(''एच, पेरेंट(i)'') | ||
अन्य: | अन्य: | ||
पुश-अप-मिन(''एच'', ''आई'') | पुश-अप-मिन(''एच'', ''आई'') | ||
यदि अंत | |||
अन्य: | अन्य: | ||
यदि ''h[i] < h[parent(i)]'' तो: | यदि ''h[i] < h[parent(i)]'' तो: | ||
| Line 152: | Line 156: | ||
पुश-अप-मिन(''एच, पेरेंट(i)'') | पुश-अप-मिन(''एच, पेरेंट(i)'') | ||
अन्य: | अन्य: | ||
पुश-अप- | पुश-अप-अधिकतम(''एच'', ''आई'') | ||
यदि अंत | |||
यदि अंत | |||
यदि अंत | |||
==== पुश अप न्यूनतम ==== | ==== पुश अप न्यूनतम ==== | ||
फलन पुश-अप-मिन(''एच'', ''आई''): | |||
यदि ''i'' के दादा-दादी हैं और ''h[i] < h[grandparent(i)]'' तो: | यदि ''i'' के दादा-दादी हैं और ''h[i] < h[grandparent(i)]'' तो: | ||
''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें | ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें | ||
पुश-अप-मिन(''एच, दादा-दादी(i)'') | पुश-अप-मिन(''एच, दादा-दादी(i)'') | ||
यदि अंत | |||
==== अधिकतम पुश अप ==== | ==== अधिकतम पुश अप ==== | ||
के साथ के रूप में <code>push-down</code> | के साथ के रूप में <code>push-down</code> ऑपरेशन, <code>push-up-max</code> के समान है <code>push-up-min</code>, लेकिन तुलनात्मक ऑपरेटरों के साथ उलट: | ||
फलन पुश-अप-अधिकतम(''एच'', ''आई''): | |||
यदि ''i'' के दादा-दादी हैं और ''h[i] > h[दादा-दादी(i)]'' तो: | यदि ''i'' के दादा-दादी हैं और ''h[i] > h[दादा-दादी(i)]'' तो: | ||
''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें | ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें | ||
पुश-अप- | पुश-अप-अधिकतम(''एच, दादा-दादी(i)'') | ||
यदि अंत | |||
==== पुनरावृत्त प्रपत्र ==== | ==== पुनरावृत्त प्रपत्र ==== | ||
जैसा कि पुनरावर्ती कॉल करता है <code>push-up-min</code> और <code>push-up-max</code> पूंछ की स्थिति में हैं, इन कार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में भी परिवर्तित किया जा सकता है: | जैसा कि पुनरावर्ती कॉल करता है <code>push-up-min</code> और <code>push-up-max</code> पूंछ की स्थिति में हैं, इन कार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में भी परिवर्तित किया जा सकता है: | ||
फलन पुश-अप-न्यूनतम-इटर(''एच'', ''आई''): | |||
जबकि ''i'' के दादा-दादी हैं और ''h[i] < h[grandparent(i)]'' तो: | जबकि ''i'' के दादा-दादी हैं और ''h[i] < h[grandparent(i)]'' तो: | ||
''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें | ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें | ||
| Line 182: | Line 186: | ||
==== उदाहरण ==== | ==== उदाहरण ==== | ||
यहां | यहां न्यूनतम-अधिकतम हीप में अवयव डालने का उदाहरण दिया गया है। | ||
मान लें कि हमारे पास निम्नलिखित न्यूनतम-अधिकतम | मान लें कि हमारे पास निम्नलिखित न्यूनतम-अधिकतम हीप है और हम मान 6 के साथ नवीन नोड सम्मिलित करना चाहते हैं। | ||
::[[File:Min-max heap.jpg|400px|न्यूनतम-अधिकतम ढेर का उदाहरण]]प्रारंभ में, नोड 6 को नोड 11 के दाएं बच्चे के रूप में डाला गया है। 6, 11 से कम है, इसलिए यह अधिकतम स्तर (41) पर सभी नोड्स से कम है, और हमें केवल न्यूनतम स्तर (8 और 11) की जांच करने की आवश्यकता है ) | ::[[File:Min-max heap.jpg|400px|न्यूनतम-अधिकतम ढेर का उदाहरण]]प्रारंभ में, नोड 6 को नोड 11 के दाएं बच्चे के रूप में डाला गया है। 6, 11 से कम है, इसलिए यह अधिकतम स्तर (41) पर सभी नोड्स से कम है, और हमें केवल न्यूनतम स्तर (8 और 11) की जांच करने की आवश्यकता है )। हमें नोड्स 6 और 11 को स्वैप करना चाहिए और फिर 6 और 8 को स्वैप करना चाहिए। तो, 6 को हीप की मूल स्थिति में ले जाया जाता है, पूर्व रूट 8 को 11 की जगह लेने के लिए नीचे ले जाया जाता है, और 11 8 का सही बच्चा बन जाता है। | ||
6 के बजाय | 6 के बजाय नवीन नोड 81 जोड़ने पर विचार करें। प्रारंभ में, नोड को नोड 11 के दाहिने बच्चे के रूप में डाला जाता है। 81, 11 से बड़ा है, इसलिए यह किसी भी न्यूनतम स्तर (8 और 11) पर किसी भी नोड से बड़ा है। अब, हमें केवल अधिकतम स्तर (41) पर नोड्स की जांच करने और स्वैप करने की आवश्यकता है। | ||
=== न्यूनतम खोजें === | === न्यूनतम खोजें === | ||
न्यूनतम-अधिकतम हीप का न्यूनतम नोड (या डुप्लिकेट कुंजियों के मामले में न्यूनतम नोड) हमेशा रूट पर स्थित होता है। न्यूनतम खोजें इस प्रकार तुच्छ स्थिर | |||