View source for मिन-मैक्स हीप

{{Short description|Computer data structure}}
{{Infobox data structure
|name=Min-max heap
|type=binary tree/heap
|presented_by= M. D. Atkinson, J. R. Sack, N. Santoro, T. Strothotte
|invented_year=1986
|insert_avg={{math|O(log  n)}}
|insert_worst={{math|O(log n)}}
|delete_avg={{math|O(log  n)}} <ref name="How to perform a general deletion operation on a min-max heap?">{{cite web|last1=Mischel|title=Jim|url=https://stackoverflow.com/a/39393768|website=Stack Overflow|access-date=8 September 2016}}</ref>
|delete_worst={{math|O(log n)}} 
}}

[[कंप्यूटर विज्ञान]] में, मिन-मैक्स हीप पूर्ण [[ द्विआधारी वृक्ष |बाइनरी ट्री]] [[डेटा संरचना]] है जो '''मिन-हीप''' और मैक्स-हीप दोनों की उपयोगिता को जोड़ती है, अर्थात, यह मिन और मैक्स दोनों अवयवों की निरंतर समय पुनर्प्राप्ति और लॉगरिदमिक समय निष्कासन प्रदान करती है।<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|मिन-मैक्स हीप का उदाहरण]]

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

* मूल अवयव मिन-मैक्स हीप में सबसे छोटा अवयव है।
* दूसरे स्तर के दो अवयवों में से एक है, जो मैक्स (या विषम) स्तर है, मिन-मैक्स हीप में सबसे बड़ा अवयव है।
* मान लीजिए <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" />) इस प्रकार है:

 '''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'''

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

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

 '''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'''

==== पुनरावृत्त रूप ====
चूंकि <code>push-down-min</code> और <code>push-down-max</code> पुनरावर्ती कॉल पश्च की स्थिति में हैं, इस प्रकार से इन प्रकार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:
 '''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'''

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

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

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

=== पुश अप ===
<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>) इस प्रकार है:
 '''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'''

==== मैक्स पुश अप ====
<code>push-down</code> ऑपरेशन के जैसे, <code>push-up-max</code> <code>push-up-min</code> के समान है, परन्तु तुलनात्मक ऑपरेटरों के विपरीत:
 '''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'''

==== पुनरावृत्त रूप ====
चूंकि <code>push-up-min</code> और <code>push-up-max</code> के लिए पुनरावर्ती कॉल पश्च की स्थिति में पूर्ण रूप से हैं, इसलिए इन प्रकार्यों को भी निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:
 '''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 के साथ नवीन नोड को पूर्ण रूप से सम्मिलित करना चाहते हैं।

::[[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) पर नोड की फाइंड करने और स्वैप करने की आवश्यकता है।

=== फाइंड मिन ===

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

=== फाइंड मैक्स ===

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

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

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

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

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

== संदर्भ ==
{{Reflist}}
*

[[Category:CS1 English-language sources (en)]]
[[Category:CS1 errors]]
[[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:प्राथमिकता कतारें]]