🐲 👩🏿‍🚒 🖐🏽 N- पिरामिड द्वारा क्रमबद्ध 〽️ 🕙 🦖

हेबे पर एक ढेर में छंटनी (यह भी एक पिरामिड की छंटाई है) पहले से ही एक या दो बार से अधिक अच्छे शब्द के साथ याद किया गया है, लेकिन यह हमेशा काफी प्रसिद्ध जानकारी रही है। सामान्य बाइनरी हीप को हर कोई जानता है, लेकिन एल्गोरिदम का सिद्धांत भी है: एक

एन-हीप; लियोनार्डो संख्या के आधार पर ढेर का एक गुच्छा; डेरैमाइड (ढेर का संकर और बाइनरी सर्च ट्री); टूर्नामेंट मिनी-ढेर; दर्पण (उल्टा) ढेर; कमजोर ढेर; जंग का ढेर; द्विपद ढेर; और ईश्वर जानता है कि अन्य क्या कर रहे हैं ...

और विभिन्न वर्षों में कंप्यूटर विज्ञान के सबसे चतुर प्रतिनिधियों ने इन पिरामिड संरचनाओं का उपयोग करके अपने सॉर्टिंग एल्गोरिदम का प्रस्ताव रखा। कौन परवाह करता है कि उन्होंने क्या किया है - उन लोगों के लिए हम इन संरचनाओं का उपयोग करके छंटाई के लिए समर्पित लेखों की एक छोटी श्रृंखला शुरू कर रहे हैं। ढेर की दुनिया विविध है - मुझे आशा है कि आप रुचि लेंगे।

यह लेख EDISON के समर्थन से लिखा गया था।

हम मोबाइल एप्लिकेशन के विकास में लगे हुए हैं और सॉफ्टवेयर परीक्षण सेवाएं प्रदान करते हैं ।

हम एल्गोरिदम के सिद्धांत से प्यार करते हैं! ;-)

एल्गोरिदम का एक ऐसा वर्ग है - पसंद द्वारा छँटाई। सामान्य विचार यह है कि सरणी का अनियंत्रित हिस्सा इस तथ्य के कारण कम हो जाता है कि यह अधिकतम तत्वों की खोज करता है जो इसे एक बढ़ते सॉर्ट किए गए क्षेत्र में पुन: व्यवस्थित करते हैं।

सामान्य पसंद को छाँटना क्रूर बल है। यदि, मैक्सिमा की खोज में, यह सरणी के माध्यम से रैखिक रूप से जाना सरल है, तो इस तरह के एक एल्गोरिथ्म की समय जटिलता O ( n ² ) से अधिक नहीं हो सकती है ।

एक गुच्छा

सरणी में उच्चियों के साथ काम करने का सबसे कुशल तरीका डेटा को एक विशेष वृक्ष संरचना में व्यवस्थित करना है, जिसे एक ढेर के रूप में जाना जाता है । यह एक ऐसा पेड़ है जिसमें सभी मूल नोड्स वंशज नोड्स से कम नहीं हैं।

ढेर के अन्य नाम - पिरामिड , सॉर्टिंग ट्री ।

आइए देखें कि एक सरणी को पेड़ के रूप में पेश करने के लिए यह आसानी से और लगभग मुफ्त कैसे हो सकता है।

सरणी का पहला तत्व लें और विचार करें कि यह पेड़ की जड़ है - 1 स्तर का एक नोड। अगले 2 तत्व 2 के स्तर के नोड हैं, मूल तत्व के दाएं और बाएं वंशज। अगले 4 तत्व 3 स्तर के नोड हैं, सरणी के दूसरे / तीसरे तत्व के दाएं / बाएं वंशज। अगले 8 तत्व चौथे स्तर के नोड हैं, तीसरे स्तर के तत्वों के वंशज। आदि। इस छवि में, बाइनरी ट्री के नोड्स स्पष्ट रूप से सरणी में संबंधित तत्वों के नीचे सख्ती से स्थित हैं:

हालाँकि, आरेख में पेड़ों को अक्सर इस तरह के स्कैन में दर्शाया जाता है:

यदि आप इस कोण को देखते हैं, तो यह स्पष्ट है कि क्यों एक गुच्छा द्वारा छंटाई को पिरामिडल छँटाई कहा जाता है। हालाँकि, यह उसी के बारे में है जैसे कि आप एक शतरंज के हाथी को एक अधिकारी, एक बदमाश, एक तुरा और एक रानी को रानी कहते हैं। I -th तत्व

के वंशजों के लिए संकेत प्राथमिक द्वारा निर्धारित किया जाता है (यदि प्रोग्रामिंग भाषाओं के बहुमत में प्रथागत माना जाता है, तो सरणी के पहले तत्व का सूचकांक): 2 × i + 1 के बाएं वंशज , दाएं बच्चे: 2 × i + 2 (मैं चार्ट पर हूं) और एनिमेशन में, पारंपरिक रूप से, सरणियों के अनुक्रम 1 से शुरू होते हैं, जहां सूत्र थोड़े अलग होते हैं: बाएं बच्चा: 2 × i और दायां बच्चा: 2 × i + 1

, लेकिन ये पहले से ही छोटे अंकगणितीय बारीकियां हैं)।

यदि इन योगों से उत्पन्न संतति सूचकांकों को सरणी से परे जाते हैं, तो इसका मतलब है कि i -th आइटम का कोई बच्चा नहीं है। यह भी हो सकता है कि i -th तत्व एक बाएं वंशज है (सरणी के अंतिम तत्व पर होता है जिसमें विषम संख्या में तत्व होते हैं), लेकिन कोई अधिकार नहीं है।

तो, किसी भी सरणी को आसानी से एक पेड़ के रूप में दर्शाया जा सकता है, लेकिन यह अभी तक एक ढेर नहीं है, क्योंकि, सरणी में, कुछ वंश तत्व उनके मूल तत्वों से बड़े हो सकते हैं।

हमारे पेड़ के लिए, सरणी के आधार पर, ढेर बनने के लिए, इसे ठीक से निचोड़ने की आवश्यकता है।

Sifting

एक झुंड की छंटाई की आत्मा बहती है।

एक तत्व के लिए स्थानांतरण यह है कि अगर यह एक असंगत श्रृंखला में संयुक्त वंश से छोटा है, तो इस तत्व को जितना संभव हो उतना कम स्थानांतरित किया जाना चाहिए, और बड़े वंश को 1 स्तर ऊपर उठाया जाना चाहिए।

छवि आइटम के लिए स्थानांतरण पथ दिखाती है। नीला रंग उस तत्व को इंगित करता है जिसके लिए स्थानांतरण किया जाता है। ग्रीन - शाखा के नीचे बड़े वंशज। उन्हें एक स्तर ऊपर उठाया जाएगा, क्योंकि वे नीले गाँठ की तुलना में आकार में बड़े होते हैं, जिसके लिए स्क्रीन बनाई जाती है। हरे रंग की श्रृंखला से सबसे ऊपर नीले नोड से तत्व खुद को सबसे कम वंशज के स्थान पर ले जाया जाएगा।

एक साधारण पेड़ से छँटाई करने के लिए और इस (छँटाई) अवस्था में वृक्ष को आगे बढ़ाने के लिए एक छँटाई की आवश्यकता होती है।

इस छवि में, सरणी के तत्वों को पुनर्वितरित किया जाता है ताकि यह पहले से ही एक ढेर में रखी जाए। हालांकि सरणी को एक छंटाई वाले पेड़ में विघटित किया गया है, यह अभी तक छंटनी नहीं हुई है (या तो आरोही या अवरोही), हालांकि पेड़ में सभी वंशज अपने मूल नोड से छोटे हैं। लेकिन फिर छंटाई के पेड़ में सबसे अधिक तत्व हमेशा मुख्य जड़ में होता है, जो बहुत महत्वपूर्ण है।

हीप सॉर्ट :: हीप्सोर्ट

एल्गोरिथ्म वास्तव में सरल है:

चरण 1. हम पूरे सरणी से एक सॉर्टिंग ट्री बनाते हैं। ऐसा करने के लिए, हम तत्वों के बाएं से दाएं से गुजरते हैं (आखिरी से पहली तक) और यदि तत्व के वंशज हैं, तो हम इसके लिए एक दरार बनाते हैं।
2. . , . ( ) . , .. . , — . , .

एक क्लासिक पिरामिड प्रकार के कार्यान्वयन के लिए पायथन कोड:

#    
def HeapSort(data):

    #    
    #   -   
    # (   )       
    for start in range((len(data) - 2) / 2, -1, -1):
        HeapSift(data, start, len(data) - 1) 

    #        
    #        .
    for end in range(len(data) - 1, 0, -1): 
        #       
        #    
        data[end], data[0] = data[0], data[end]
        #        
        #   
        #     
        HeapSift(data, 0, end - 1)
    return data

#   ,      
def HeapSift(data, start, end):

    #   - ,     
    root = start 
    
    #      ,
    #   ,    
    while True:

        child = root * 2 + 1 #  
        #      -  
        if child > end: break 

        #       ,
        #      
        if child + 1 <= end and data[child] < data[child + 1]:
            child += 1

        #     ,   
        #       , 
        #       
        if data[root] < data[child]:
            data[root], data[child] = data[child], data[root]
            root = child
        else:
            break

एल्गोरिथ्म जटिलता

एक साधारण ढेर क्यों अच्छा है - इसे अन्य प्रकार के पेड़ों के विपरीत अलग से संग्रहीत करने की आवश्यकता नहीं है (उदाहरण के लिए, उपयोग के पहले एक सरणी पर आधारित एक द्विआधारी खोज पेड़ बनाया जाना चाहिए)। कोई भी सरणी पहले से ही एक पेड़ है जिसमें, जाने पर सही, आप तुरंत माता-पिता और वंशज की पहचान कर सकते हैं। अतिरिक्त मेमोरी की जटिलता ओ ( 1 ) है, सब कुछ तुरंत होता है।

समय की जटिलता के लिए, यह स्थानांतरण पर निर्भर करता है। O (लॉग एन ) में एक एकल स्थानांतरण को बाईपास किया गया है । पहले, हम सरणी से प्रारंभिक ढेर बनाने के लिए n तत्वों के लिए एक दरार बनाते हैं - यह कदम O ( n लॉग एन ) लेता है । दूसरे चरण में, जब हम एन को बाहर निकालते हैंढेर से वर्तमान अधिकतम, हम शेष भाग के लिए एक ही स्थानांतरण करते हैं, अर्थात्। इस चरण में हमें O ( n लॉग एन ) भी खर्च होता है ।

कुल समय जटिलता: ओ ( एन लॉग एन ) + ओ ( एन लॉग एन ) = ओ ( एन लॉग एन )।
इसके अलावा, पिरामिड की छँटाई में न तो पतित होते हैं और न ही बेहतर मामले। किसी भी सरणी को एक सभ्य गति से संसाधित किया जाएगा, लेकिन कोई गिरावट या रिकॉर्ड नहीं होगा।

औसत छँटाई में छँटाई औसत छँटाई की तुलना में थोड़ी धीमी होती है। लेकिन क्विकॉर्ट के लिए, आप एक हत्यारे सरणी उठा सकते हैं, जिस पर कंप्यूटर लटका हुआ है, लेकिन हेप्सॉर्ट के लिए - नहीं।

समय की जटिलता
सबसे खराब	औसत	सबसे अच्छा
O(n log n)
O(n²)	O(n log n)	O(n)

:: Ternary heapsort

आइए टर्नरी ढेर को देखें। आप इसे बाइनरी से विश्वास नहीं करेंगे, यह केवल इस बात में भिन्न है कि मूल नोड्स में अधिकतम दो नहीं, बल्कि तीन वंशज हैं। के लिए त्रिगुट ढेर में मैं मई के तत्व कोड यह तीन संतानों समान गणना (यदि पहला तत्व सूचकांक = 0):

बाईं वंशज 3 × मैं +1
मध्य वंशज 3 × मैं + 2
सही वंशज 3 × मैं + 3

(यदि इंडेक्स 1 से शुरू होता है, जैसा कि इस लेख में एनिमेशन में है, तो इन फॉर्मूलों में आपको बस एक को घटाना होगा)।

छँटाई प्रक्रिया:

एक ओर, बाइनरी ढेर की तुलना में पेड़ में स्तरों की संख्या में स्पष्ट रूप से कमी आती है, जिसका अर्थ है कि औसतन, स्थानांतरण के दौरान कम स्वैप होंगे। दूसरी ओर, न्यूनतम वंशज को खोजने के लिए, अधिक तुलना की आवश्यकता होगी - क्योंकि वंशज अब दो नहीं हैं, लेकिन प्रत्येक तीन हैं। सामान्य तौर पर, समय की जटिलता के संदर्भ में - कहीं हम पाते हैं, कहीं हम खोते हैं, लेकिन सामान्य रूप से एक ही चीज। टर्नरी ढेर में डेटा बाइनरी की तुलना में थोड़ा तेज सॉर्ट किया जाता है, लेकिन यह स्पीडअप बहुत छोटा है। पिरामिड की छँटाई के सभी रूपों में, एल्गोरिदम के डेवलपर्स द्विआधारी विकल्प लेना पसंद करते हैं, क्योंकि टर्नरी को लागू करने में अधिक मुश्किल माना जाता है (हालांकि एल्गोरिथ्म में एक या तीन अतिरिक्त लाइनें जोड़ने के लिए "अधिक कठिन" है), और गति हासिल करना न्यूनतम है।

एन-हीप ढेर द्वारा क्रमबद्ध करें :: एन-नैनी हीप्सोर्ट

बेशक, आप वहां नहीं रुक सकते हैं और किसी भी वंशज के लिए एक झुंड द्वारा छंटाई को अनुकूलित कर सकते हैं। हो सकता है कि यदि आप वंश की संख्या में वृद्धि करना जारी रखते हैं, तो आप प्रक्रिया की गति को महत्वपूर्ण रूप से बढ़ा सकते हैं? सरणी सूचकांकों

के i वें तत्व के लिए (यदि शून्य की गिनती), तो इसके एन वंशज की गणना बहुत ही सरलता से की गई:

पहला वंशज: एन × आई + 1
दूसरा वंशज: एन × आई + 2
तीसरा वंशज: एन × आई + 3
...
वां वंशज: एन × मैं + N

अजगर एक एन ढेर द्वारा छँटाई के लिए कोड:

#      N 
def NHeapSort(data):

    n = 3 #    

    #    
    #   -   
    # (   )       
    for start in range(len(data), -1, -1):
        NHeapSift(data, n, start, len(data) - 1) 

    #        
    #        .
    for end in range(len(data) - 1, 0, -1): 
        #       
        #    
        data[end], data[0] = data[0], data[end]
        #        
        #   
        #     
        NHeapSift(data, n, 0, end - 1)
    return data
    
#  -     N 
def NHeapSift(data, n, start, end):
    
    #   - ,     
    root = start 

    while True:
        
        #   (    )
        #   
        child = root * n + 1
        if child > end: 
            break 

        max = child
        
        #    
        for k in range(2, n + 1):
            current = root * n + k
            if current > end:
                break
                
            if data[current] > data[max]:
                max = current
        
        #     
        #        
        #  
        if data[root] < data[max]:
            data[root], data[max] = data[max], data[root]
            root = max
        else:
            break

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

यदि टर्नरी का ढेर न्यूनतम रूप से बाइनरी से आगे निकल जाता है, तो चौगुनी पहले से ही खो रही है। कई के बीच अधिकतम वंश को खोजना बहुत महंगा हो जाता है।

अगली सीरीज का ट्रेलर

तो, बाइनरी / टर्नरी / एन-हीप का मुख्य नुकसान इसकी जटिलता में कूदने की अक्षमता ओ ( एन लॉग एन ) से अधिक है । गतिरोध का तरीका छंटाई में अधिक परिष्कृत ढेर किस्मों का उपयोग करना है। एक सप्ताह में हम इस बारे में परिचित हो जाएंगे कि एग्जेर दिज्कस्ट्रा इस बारे में क्या सोचता है।

एक गुच्छा द्वारा निम्नलिखित छंटाई के साथ लेख पर जाने के लिए एनीमेशन पर क्लिक करें

संदर्भ

ढेर / पिरामिड

श्रृंखला लेख:

एक्सेल आवेदन AlgoLab.xlsm
एक्सचेंज सॉर्ट
निवेशन शॉर्ट्स
चयन के आधार पर छाँटें
- हीप शॉर्ट्स: एन-पिरामिड
- हीप सॉर्ट्स: लियोनार्डो नंबर
- ढेर की तरह: कमजोर ढेर
- बंच सॉर्ट्स: कार्टेशियन ट्री
- अन्य ढेर छँटाई: दर्पण ढेर, मिनी-ढेर, नीचे-ऊपर स्थानांतरण
- हीप सॉर्ट्स: जंग हीप
मर्ज करना
वितरण के आधार पर छाँटें
हाइब्रिड सॉर्टिंग

AlgoLab एप्लिकेशन को एन-हीप द्वारा छँटाई गयी। वंश की संख्या का चयन करने के लिए, इस प्रकार के सेल पर टिप्पणी में, आपको n के लिए एक संख्या निर्दिष्ट करने की आवश्यकता है। संभावित मानों की सीमा 2 से 5 तक है (यह कोई मतलब नहीं है, क्योंकि n> = 6 के लिए, सामान्य स्तर पर तीन स्तरों के घोंसले के शिकार के साथ एनीमेशन स्क्रीन पर फिट होने की गारंटी नहीं है)।

N- पिरामिड द्वारा क्रमबद्ध