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

Min-max heap
Min-max heap
Type	binary tree/heap
Invented	1986
Time complexity in big O notation
Algorithm
Algorithm	Average
Insert	O(log n)
Delete	O(log n)

Revision as of 22:42, 21 July 2023

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

न्यूनतम-अधिकतम हीप का उदाहरण

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

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

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

ऑपरेशन

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

बिल्ड

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

function FLOYD-BUILD-HEAP(h):

    for each index i from  $\lfloor length(h)/2\rfloor$  down to 1 do:

        push-down(h, i)
    return h

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

=== नीचे दबाएं === push-down ई> एल्गोरिदम (या trickle-down जैसा कि इसमें कहा जाता है ^[4]) इस प्रकार है:

फलन पुश-डाउन(एच, आई):
    यदि i न्यूनतम स्तर पर है तो:
        पुश-डाउन-मिन(एच, आई)
    अन्य:
        पुश-डाउन-अधिकतम(एच, आई)
    यदि अंत

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

फलन पुश-डाउन-मिन(एच, आई):
    यदि मेरे के बच्चे हैं तो:
        m := i के सबसे छोटे बच्चे या पोते का सूचकांक
        यदि m i का पोता है तो:
            यदि h[m] < h[i] तो:
                h[m] और h[i] की अदला-बदली करें
                यदि h[m] > h[parent(m)] तो:
                    h[m] और h[parent(m)] को स्वैप करें
                यदि अंत
                पुश-डाउन(एच, एम)
            यदि अंत
        अन्यथा यदि h[m] < h[i] तो:
            h[m] और h[i] की अदला-बदली करें
        यदि अंत
    यदि अंत

अधिकतम नीचे पुश करें

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

फलन पुश-डाउन-अधिकतम(एच, आई):
    यदि मेरे के बच्चे हैं तो:
        m := i के सबसे बड़े बच्चे या पोते का सूचकांक
        यदि m i का पोता है तो:
            यदि h[m] > h[i] तो:
                h[m] और h[i] की अदला-बदली करें
                यदि h[m] < h[parent(m)] तो:
                    h[m] और h[parent(m)] को स्वैप करें
                यदि अंत
                पुश-डाउन(एच, एम)
            यदि अंत
        अन्यथा यदि h[m] > h[i] तो:
            h[m] और h[i] की अदला-बदली करें
        यदि अंत
    यदि अंत

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

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

फलन पुश-डाउन-इटर(एच, एम):
    जबकि m के बच्चे हैं तो:
        मैं := एम
        यदि i न्यूनतम स्तर पर है तो:
            m := i के सबसे छोटे बच्चे या पोते का सूचकांक
            यदि h[m] < h[i] तो:
                h[m] और h[i] की अदला-बदली करें
                यदि m i का पोता है तो:
                    यदि h[m] > h[parent(m)] तो:
                        h[m] और h[parent(m)] को स्वैप करें
                    यदि अंत
                अन्य
                    तोड़ना
                यदि अंत
            अन्य
                तोड़ना
            यदि अंत
        अन्य:
            m := i के सबसे बड़े बच्चे या पोते का सूचकांक
            यदि h[m] > h[i] तो:
                h[m] और h[i] की अदला-बदली करें
                यदि m i का पोता है तो:
                    यदि h[m] < h[parent(m)] तो:
                        h[m] और h[parent(m)] को स्वैप करें
                    यदि अंत
                अन्य
                    तोड़ना
                यदि अंत
            अन्य
                तोड़ना
            यदि अंत
        यदि अंत
    अंत तक

निवेशन

न्यूनतम-अधिकतम हीप में अवयव जोड़ने के लिए निम्नलिखित कार्य करें:

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

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

=== पुश अप === push-up ई> एल्गोरिदम (या bubble-up जैसा कि इसमें कहा जाता है ^[7] ) इस प्रकार है:

फलन पुश-अप(एच, आई):
    यदि i जड़ नहीं है तो:
        यदि i न्यूनतम स्तर पर है तो:
            यदि h[i] > h[parent(i)] तो:
                h[i] और h[parent(i)] को स्वैप करें
                पुश-अप-अधिकतम(एच, पेरेंट(i))
            अन्य:
                पुश-अप-मिन(एच, आई)
            यदि अंत
        अन्य:
            यदि h[i] < h[parent(i)] तो:
                h[i] और h[parent(i)] को स्वैप करें
                पुश-अप-मिन(एच, पेरेंट(i))
            अन्य:
                पुश-अप-अधिकतम(एच, आई)
            यदि अंत
        यदि अंत
    यदि अंत

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

फलन पुश-अप-मिन(एच, आई):
    यदि i के दादा-दादी हैं और h[i] < h[grandparent(i)] तो:
        h[i] और h[दादा-दादी(i)] की अदला-बदली करें
        पुश-अप-मिन(एच, दादा-दादी(i))
    यदि अंत

अधिकतम पुश अप

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

फलन पुश-अप-अधिकतम(एच, आई):
    यदि i के दादा-दादी हैं और h[i] > h[दादा-दादी(i)] तो:
        h[i] और h[दादा-दादी(i)] की अदला-बदली करें
        पुश-अप-अधिकतम(एच, दादा-दादी(i))
    यदि अंत

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

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

फलन पुश-अप-न्यूनतम-इटर(एच, आई):
    जबकि i के दादा-दादी हैं और h[i] < h[grandparent(i)] तो:
        h[i] और h[दादा-दादी(i)] की अदला-बदली करें
        मैं := दादा-दादी(i)
    अंत तक

उदाहरण

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

मान लें कि हमारे पास निम्नलिखित न्यूनतम-अधिकतम हीप है और हम मान 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 फिर हीप प्रॉपर्टी को पुनर्स्थापित करने के लिए रूट इंडेक्स पर कॉल किया जाता है $O(\log _{2}(n))$ समय।

अधिकतम हटाएं

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

एक्सटेंशन

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

संदर्भ

↑ Mischel. "Jim". Stack Overflow. Retrieved 8 September 2016.
↑ ^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.
↑ 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.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.
↑ Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). Handbook of Algorithms and Data Structures: In Pascal and C. ISBN 0201416077.
↑ K. Paparrizos, Ioannis (2011). "फ्लोयड के ढेर निर्माण एल्गोरिदम के लिए तुलनाओं की सबसे खराब स्थिति की संख्या पर एक सख्त बंधन". arXiv:1012.0956. Bibcode:2010arXiv1012.0956P. {{cite journal}}: Cite journal requires |journal= (help)
↑ 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.

[How_to_perform_a_general_deletion_operation_on_a_min-max_heap?-1] Mischel. "Jim". Stack Overflow. Retrieved 8 September 2016.

[:0-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.

[:1-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ 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> (संरचना में kth सबसे छोटा मान निर्धारित करें) और ऑपरेशन <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.key</math> रूट के साथ सबट्री में सभी कुंजियों के बीच न्यूनतम कुंजी है <math>x</math>.
+* मूल अवयव न्यूनतम-अधिकतम हीप में सबसे छोटा अवयव है।
-** अगर <math>x</math> तो, अधिकतम (या विषम) स्तर पर है <math>x.key</math> रूट के साथ सबट्री की सभी कुंजियों में से अधिकतम कुंजी है <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> अधिकतम कुंजी है।
 * न्यूनतम (अधिकतम) स्तर पर नोड को न्यूनतम (अधिकतम) नोड कहा जाता है।
-अधिकतम-न्यूनतम ढेर को समान रूप से परिभाषित किया गया है; ऐसे ढेर में, अधिकतम मूल्य रूट पर संग्रहीत होता है, और सबसे छोटा मूल्य रूट के बच्चों में से पर संग्रहीत होता है।<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> h> सरणी में स्थान स्तर पर स्थित नोड के अनुरूप होगा <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''):
- फ़ंक्शन फ़्लॉइड-बिल्ड-हीप(''एच''):
+     '''for''' each index ''i'' from <math>\lfloor length(h) / 2 \rfloor</math> '''down to''' 1 '''do:'''
-     प्रत्येक सूचकांक ''i'' के लिए <math>\lfloor length(h) / 2 \rfloor</math>1 से नीचे करें:
-         पुश-डाउन(''एच'', ''आई'')
-     वापसी ज
-इस फ़ंक्शन में, ''h'' प्रारंभिक सरणी है, जिसके तत्वों को न्यूनतम-अधिकतम ढेर संपत्ति के अनुसार क्रमबद्ध नहीं किया जा सकता है। <code>push-down</code> ई> न्यूनतम-अधिकतम ढेर के संचालन (जिसे कभी-कभी हेपिफाई भी कहा जाता है) को आगे समझाया गया है।
+         '''push-down'''(''h'', ''i'')
+     '''return''' h
+इस फलन में, ''h'' प्रारंभिक सरणी है, जिसके अवयवों को न्यूनतम-अधिकतम हीप गुण के अनुसार क्रमबद्ध नहीं किया जा सकता है। <code>push-down</code> ई> न्यूनतम-अधिकतम हीप के ऑपरेशन (जिसे कभी-कभी हेपिफाई भी कहा जाता है) को आगे समझाया गया है।
 === नीचे दबाएं === <code>push-down</code> ई> एल्गोरिदम (या <code>trickle-down</code> जैसा कि इसमें कहा जाता है <ref name=":1" />) इस प्रकार है:
-  फ़ंक्शन पुश-डाउन(''एच'', ''आई''):
+  फलन पुश-डाउन(''एच'', ''आई''):
       यदि ''i'' न्यूनतम स्तर पर है तो:
           पुश-डाउन-मिन(''एच'', ''आई'')
       अन्य:
-          पुश-डाउन-मैक्स(''एच'', ''आई'')
+          पुश-डाउन-अधिकतम(''एच'', ''आई'')
-      अगर अंत
+      यदि अंत
 ==== पुश डाउन न्यूनतम ====
-  फ़ंक्शन पुश-डाउन-मिन(''एच'', ''आई''):
+  फलन पुश-डाउन-मिन(''एच'', ''आई''):
       यदि ''मेरे'' के बच्चे हैं तो:
           ''m'' := ''i'' के सबसे छोटे बच्चे या पोते का सूचकांक
@@ Line 62: / Line 66: @@
                   यदि ''h[m]'' > ''h[parent(m)]'' तो:
                       ''h[m]'' और ''h[parent(m)]'' को स्वैप करें
-                  अगर अंत
+                  यदि अंत
                   पुश-डाउन(''एच'', ''एम'')
-              अगर अंत
+              यदि अंत
           अन्यथा यदि ''h[m]'' < ''h[i]'' तो:
               ''h[m]'' और ''h[i]'' की अदला-बदली करें
-          अगर अंत
+          यदि अंत
-      अगर अंत
+      यदि अंत
 ==== अधिकतम नीचे पुश करें ====
@@ Line 74: / Line 78: @@
 के लिए एल्गोरिदम <code>push-down-max</code> पुश-डाउन-मिन के समान है, लेकिन सभी तुलना ऑपरेटर उलट गए हैं।
-  फ़ंक्शन पुश-डाउन-मैक्स(''एच'', ''आई''):
+  फलन पुश-डाउन-अधिकतम(''एच'', ''आई''):
       यदि ''मेरे'' के बच्चे हैं तो:
           ''m'' := ''i'' के सबसे बड़े बच्चे या पोते का सूचकांक
@@ Line 82: / Line 86: @@
                   यदि ''h[m]'' < ''h[parent(m)]'' तो:
                       ''h[m]'' और ''h[parent(m)]'' को स्वैप करें
-                  अगर अंत
+                  यदि अंत
                   पुश-डाउन(''एच'', ''एम'')
-              अगर अंत
+              यदि अंत
           अन्यथा यदि ''h[m]'' > ''h[i]'' तो:
               ''h[m]'' और ''h[i]'' की अदला-बदली करें
-          अगर अंत
+          यदि अंत
-      अगर अंत
+      यदि अंत
 ==== पुनरावृत्त प्रपत्र ====
 जैसे ही पुनरावर्ती कॉल आती है <code>push-down-min</code> और <code>push-down-max</code> पूंछ की स्थिति में हैं, इन कार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में परिवर्तित किया जा सकता है:
-  फ़ंक्शन पुश-डाउन-इटर(''एच'', ''एम''):
+  फलन पुश-डाउन-इटर(''एच'', ''एम''):
       जबकि ''m'' के बच्चे हैं तो:
           ''मैं := एम''
@@ Line 102: / Line 106: @@
                       यदि ''h[m]'' > ''h[parent(m)]'' तो:
                           ''h[m]'' और ''h[parent(m)]'' को स्वैप करें
-                      अगर अंत
+                      यदि अंत
                   अन्य
                       तोड़ना
-                  अगर अंत
+                  यदि अंत
               अन्य
                   तोड़ना
-              अगर अंत
+              यदि अंत
           अन्य:
               ''m'' := ''i'' के सबसे बड़े बच्चे या पोते का सूचकांक
@@ Line 116: / Line 120: @@
                       यदि ''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>
 ) इस प्रकार है:
-  फ़ंक्शन पुश-अप(''एच'', ''आई''):
+  फलन पुश-अप(''एच'', ''आई''):
       यदि ''i'' जड़ नहीं है तो:
           यदि ''i'' न्यूनतम स्तर पर है तो:
               यदि ''h[i] > h[parent(i)]'' तो:
                   ''h[i]'' और ''h[parent(i)]'' को स्वैप करें
-                  पुश-अप-मैक्स(''एच, पेरेंट(i)'')
+                  पुश-अप-अधिकतम(''एच, पेरेंट(i)'')
               अन्य:
                   पुश-अप-मिन(''एच'', ''आई'')
-              अगर अंत
+              यदि अंत
           अन्य:
               यदि ''h[i] < h[parent(i)]'' तो:
@@ Line 152: / Line 156: @@
                   पुश-अप-मिन(''एच, पेरेंट(i)'')
               अन्य:
-                  पुश-अप-मैक्स(''एच'', ''आई'')
+                  पुश-अप-अधिकतम(''एच'', ''आई'')
-              अगर अंत
+              यदि अंत
-          अगर अंत
+          यदि अंत
-      अगर अंत
+      यदि अंत
 ==== पुश अप न्यूनतम ====
-  फ़ंक्शन पुश-अप-मिन(''एच'', ''आई''):
+  फलन पुश-अप-मिन(''एच'', ''आई''):
       यदि ''i'' के दादा-दादी हैं और ''h[i] < h[grandparent(i)]'' तो:
           ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें
           पुश-अप-मिन(''एच, दादा-दादी(i)'')
-      अगर अंत
+      यदि अंत
 ==== अधिकतम पुश अप ====
-के साथ के रूप में <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>, लेकिन तुलनात्मक ऑपरेटरों के साथ उलट:
-  फ़ंक्शन पुश-अप-मैक्स(''एच'', ''आई''):
+  फलन पुश-अप-अधिकतम(''एच'', ''आई''):
       यदि ''i'' के दादा-दादी हैं और ''h[i] > h[दादा-दादी(i)]'' तो:
           ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें
-          पुश-अप-मैक्स(''एच, दादा-दादी(i)'')
+          पुश-अप-अधिकतम(''एच, दादा-दादी(i)'')
-      अगर अंत
+      यदि अंत
 ==== पुनरावृत्त प्रपत्र ====
 जैसा कि पुनरावर्ती कॉल करता है <code>push-up-min</code> और <code>push-up-max</code> पूंछ की स्थिति में हैं, इन कार्यों को निरंतर स्थान में निष्पादित होने वाले विशुद्ध रूप से पुनरावृत्त रूपों में भी परिवर्तित किया जा सकता है:
-  फ़ंक्शन पुश-अप-मिन-इटर(''एच'', ''आई''):
+  फलन पुश-अप-न्यूनतम-इटर(''एच'', ''आई''):
       जबकि ''i'' के दादा-दादी हैं और ''h[i] < h[grandparent(i)]'' तो:
           ''h[i]'' और ''h[दादा-दादी(i)]'' की अदला-बदली करें
@@ Line 182: / Line 186: @@
 ==== उदाहरण ====
-यहां मिन-मैक्स हीप में तत्व डालने का उदाहरण दिया गया है।
+यहां न्यूनतम-अधिकतम हीप में अवयव डालने का उदाहरण दिया गया है।
-मान लें कि हमारे पास निम्नलिखित न्यूनतम-अधिकतम ढेर है और हम मान 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 का सही बच्चा बन जाता है।
-के बजाय नया नोड 81 जोड़ने पर विचार करें। प्रारंभ में, नोड को नोड 11 के दाहिने बच्चे के रूप में डाला जाता है। 81, 11 से बड़ा है, इसलिए यह किसी भी न्यूनतम स्तर (8 और 11) पर किसी भी नोड से बड़ा है। अब, हमें केवल अधिकतम स्तर (41) पर नोड्स की जांच करने और स्वैप करने की आवश्यकता है।
+के बजाय नवीन नोड 81 जोड़ने पर विचार करें। प्रारंभ में, नोड को नोड 11 के दाहिने बच्चे के रूप में डाला जाता है। 81, 11 से बड़ा है, इसलिए यह किसी भी न्यूनतम स्तर (8 और 11) पर किसी भी नोड से बड़ा है। अब, हमें केवल अधिकतम स्तर (41) पर नोड्स की जांच करने और स्वैप करने की आवश्यकता है।
 === न्यूनतम खोजें ===
-मिन-मैक्स हीप का न्यूनतम नोड (या डुप्लिकेट कुंजियों के मामले में न्यूनतम नोड) हमेशा रूट पर स्थित होता है। न्यूनतम खोजें इस प्रकार तुच्छ स्थिर समय ऑपरेशन है जो बस जड़ें लौटाता है।
+न्यूनतम-अधिकतम हीप का न्यूनतम नोड (या डुप्लिकेट कुंजियों के मामले में न्यूनतम नोड) हमेशा रूट पर स्थित होता है। न्यूनतम खोजें इस प्रकार तुच्छ स्थिर समय ऑपरेशन है जो बस जड़ें लौटाता है।
 === अधिकतम ज्ञात करें ===
-मिन-मैक्स हीप का अधिकतम नोड (या डुप्लिकेट कुंजियों के मामले में अधिकतम नोड) जिसमें से अधिक नोड होते हैं, हमेशा पहले अधिकतम स्तर पर स्थित होता है - यानी, रूट के तत्काल बच्चों में से के रूप में। अधिकतम खोजें इस प्रकार अधिकतम तुलना की आवश्यकता होती है, यह निर्धारित करने के लिए कि जड़ के दो बच्चों में से कौन सा बड़ा है, और इस तरह यह निरंतर समय ऑपरेशन भी है। यदि न्यूनतम-अधिकतम ढेर में नोड है तो वह नोड अधिकतम नोड है।
+न्यूनतम-अधिकतम हीप का अधिकतम नोड (या डुप्लिकेट कुंजियों के मामले में अधिकतम नोड) जिसमें से अधिक नोड होते हैं, हमेशा पहले अधिकतम स्तर पर स्थित होता है - अर्थात, रूट के तत्काल बच्चों में से के रूप में। अधिकतम खोजें इस प्रकार अधिकतम तुलना की आवश्यकता होती है, यह निर्धारित करने के लिए कि जड़ के दो बच्चों में से कौन सा बड़ा है, और इस तरह यह निरंतर समय ऑपरेशन भी है। यदि न्यूनतम-अधिकतम हीप में नोड है तो वह नोड अधिकतम नोड है।
 === न्यूनतम हटाएं ===
-न्यूनतम को हटाना मनमाना नोड को हटाने का विशेष मामला है जिसका सरणी में सूचकांक ज्ञात है। इस स्थिति में, सरणी का अंतिम तत्व हटा दिया जाता है (सरणी की लंबाई कम कर दी जाती है) और सरणी के शीर्ष पर रूट को बदलने के लिए उपयोग किया जाता है। <code>push-down</code> फिर हीप प्रॉपर्टी को पुनर्स्थापित करने के लिए रूट इंडेक्स पर कॉल किया जाता है <math>O(\log_2(n))</math>समय।
+न्यूनतम को हटाना मनमाना नोड को हटाने का विशेष मामला है जिसका सरणी में सूचकांक ज्ञात है। इस स्थिति में, सरणी का अंतिम अवयव हटा दिया जाता है (सरणी की लंबाई कम कर दी जाती है) और सरणी के शीर्ष पर रूट को बदलने के लिए उपयोग किया जाता है। <code>push-down</code> फिर हीप प्रॉपर्टी को पुनर्स्थापित करने के लिए रूट इंडेक्स पर कॉल किया जाता है <math>O(\log_2(n))</math>समय।
 === अधिकतम हटाएं ===
-अधिकतम को हटाना फिर से ज्ञात सूचकांक के साथ मनमाना नोड को हटाने का विशेष मामला है। जैसा कि अधिकतम खोजें ऑपरेशन में, रूट के अधिकतम बच्चे की पहचान करने के लिए एकल तुलना की आवश्यकता होती है, जिसके बाद इसे सरणी के अंतिम तत्व से बदल दिया जाता है और <code>push-down</code> फिर ढेर संपत्ति को पुनर्स्थापित करने के लिए प्रतिस्थापित अधिकतम के सूचकांक पर कॉल किया जाता है।
+अधिकतम को हटाना फिर से ज्ञात सूचकांक के साथ मनमाना नोड को हटाने का विशेष मामला है। जैसा कि अधिकतम खोजें ऑपरेशन में, रूट के अधिकतम बच्चे की पहचान करने के लिए एकल तुलना की आवश्यकता होती है, जिसके बाद इसे सरणी के अंतिम अवयव से बदल दिया जाता है और <code>push-down</code> फिर हीप गुण को पुनर्स्थापित करने के लिए प्रतिस्थापित अधिकतम के सूचकांक पर कॉल किया जाता है।
 == एक्सटेंशन ==
-न्यूनतम-अधिकतम-माध्यिका ढेर न्यूनतम-अधिकतम ढेर का प्रकार है, जो संरचना पर मूल प्रकाशन में सुझाया गया है, जो [[आदेश आँकड़ा वृक्ष]] के संचालन का समर्थन करता है।
+न्यूनतम-अधिकतम-माध्यिका हीप न्यूनतम-अधिकतम हीप का प्रकार है, जो संरचना पर मूल प्रकाशन में सुझाया गया है, जो [[आदेश आँकड़ा वृक्ष|आदेश आँकड़ा ट्री]] के ऑपरेशन का समर्थन करता है।
 == संदर्भ ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 22:42, 21 July 2023

Contents

विवरण

ऑपरेशन

बिल्ड

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

अधिकतम नीचे पुश करें

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

निवेशन

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

अधिकतम पुश अप

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

उदाहरण

न्यूनतम खोजें

अधिकतम ज्ञात करें

न्यूनतम हटाएं

अधिकतम हटाएं

एक्सटेंशन

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 22:42, 21 July 2023

विवरण

ऑपरेशन

बिल्ड

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

अधिकतम नीचे पुश करें

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

निवेशन

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

अधिकतम पुश अप

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

उदाहरण

न्यूनतम खोजें

अधिकतम ज्ञात करें

न्यूनतम हटाएं

अधिकतम हटाएं

एक्सटेंशन

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories