मिन-मैक्स हीप

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)

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

Anonymous

Search

मिन-मैक्स हीप

Namespaces

More

Page actions

Contents

विवरण

ऑपरेशन

बिल्ड

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

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

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

निवेशन

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

अधिकतम पुश अप

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

उदाहरण

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

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

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

अधिकतम हटाएं

एक्सटेंशन

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मिन-मैक्स हीप

विवरण

ऑपरेशन

बिल्ड

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

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

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

निवेशन

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

अधिकतम पुश अप

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

उदाहरण

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

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

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

अधिकतम हटाएं

एक्सटेंशन

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories