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

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) (संरचना में kth सबसे छोटा मान निर्धारित करें) और ऑपरेशन 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$ h> सरणी में स्थान स्तर पर स्थित नोड के अनुरूप होगा $\lfloor \log i\rfloor$ ढेर में.

निर्माण

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

फ़ंक्शन फ़्लॉइड-बिल्ड-हीप(एच):
    प्रत्येक सूचकांक i के लिए  $\lfloor length(h)/2\rfloor$ 1 से नीचे करें:
        पुश-डाउन(एच, आई)
    वापसी ज

इस फ़ंक्शन में, 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