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

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

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

इस प्रकार से मिन-मैक्स हीप गुण है: ट्री में सम स्तर पर प्रत्येक नोड उसके सभी वंशजों से कम है, जबकि ट्री में विषम स्तर पर प्रत्येक नोड उसके सभी वंशजों से बड़ा है।

अतः संरचना को अन्य क्रम-सांख्यिकी ऑपरेशन को कुशलतापूर्वक समर्थन देने के लिए भी सामान्यीकृत किया जा सकता है, जैसे कि find-median, delete-median,find(k) (संरचना में kवां सबसे छोटा मान निर्धारित करें) और ऑपरेशन delete(k) (संरचना में kवां सबसे छोटा मान हटाएं), k के किसी निश्चित मान (या मानों के समूह) के लिए। इन अंतिम दो ऑपरेशनों को क्रमशः स्थिर और लघुगणकीय समय में कार्यान्वित किया जा सकता है। इस प्रकार से मिन-मैक्स क्रमण की धारणा को मैक्स या मिन-क्रमण के आधार पर अन्य संरचनाओं तक बढ़ाया जा सकता है, जैसे लेफ्टिस ट्री, डेटा संरचनाओं का नवीन (और अधिक शक्तिशाली) वर्ग उत्पन्न करते हैं। अतः बाहरी क्विकसॉर्ट लागू करते समय मिन-मैक्स हीप भी उपयोगी हो सकता है।

विवरण

• मिन-मैक्स हीप पूर्ण बाइनरी ट्री है जिसमें वैकल्पिक मिन (या सम) और मैक्स (या विषम) स्तर होते हैं। इस प्रकार से सम स्तर उदाहरण के लिए 0, 2, 4, आदि हैं, और विषम स्तर क्रमशः 1, 3, 5, आदि हैं। हम अगले बिंदुओं में मानते हैं कि मूल अवयव पहले स्तर पर है, अर्थात 0।

मिन-मैक्स हीप का उदाहरण

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

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

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

ऑपरेशन

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

बिल्ड

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

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 जैसा कि इसे कहा जाता है ) इस प्रकार है:

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

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

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

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

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

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

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

इन्सर्टेसन

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

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

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

पुश अप

push-up एल्गोरिथ्म (या bubble-up जैसा कि इसे कहा जाता है) इस प्रकार है:

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

मैक्स पुश अप

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

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

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

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

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 के साथ नवीन नोड सम्मिलित करना चाहते हैं।

प्रारंभ में, नोड 6 को नोड 11 के दाएं बच्चे के रूप में डाला गया है। इस प्रकार से 6, 11 से कम है, इसलिए यह मैक्स स्तर (41) पर सभी नोड से कम है, और हमें मात्र मिन स्तर (8 और 11) की फाइंड करने की आवश्यकता है)। हमें नोड 6 और 11 को स्वैप करना चाहिए और फिर 6 और 8 को स्वैप करना चाहिए। तो, 6 को हीप की मूल स्थिति में ले जाया जाता है, पूर्व रूट 8 को 11 का स्थान लेने के लिए नीचे ले जाया जाता है, और 11 8 का दायाँ चिल्ड्रेन बन जाता है।

इस प्रकार से 6 के अतिरिक्त नवीन नोड 81 जोड़ने पर विचार करें। प्रारंभ में, नोड को नोड 11 के दाहिने बच्चे के रूप में डाला जाता है। 81, 11 से बड़ा है, इसलिए यह किसी भी मिन स्तर (8 और 11) पर किसी भी नोड से बड़ा है। अब, हमें मात्र मैक्स स्तर (41) पर नोड की फाइंड करने और स्वैप करने की आवश्यकता है।

फाइंड मिन

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

फाइंड मैक्स

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

रिमूव मिन

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

रिमूव मैक्स

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

एक्सटेंशन

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