हीप सॉर्ट

अगस्त 2020 अगस्त 2020 हीप सॉर्ट (Heapsort) बाइनरी हीप डेटा संरचना पर आधारित एक तुलना आधारित सॉर्टिंग (sorting) तकनीक है। यह चयन प्रकार के समान है, जहां हम सबसे पहले अधिकतम तत्व ढूंढते हैं और अंत में अधिकतम तत्व रखते हैं। शेष तत्व के लिए हम उसी प्रक्रिया को दोहराते हैं। बाइनरी हीप क्या है? हमें पहले एक पूर्ण बाइनरी ट्री परिभाषित करते हैं। एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है जिसमें हर स्तर, संभवतः अंतिम को छोड़कर, पूरी तरह से भरा हुआ है, और सभी नोड्स जितना संभव हो उतना बचा है (स्रोत विकिपीडिया) एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है जहां आइटम एक विशेष क्रम में संग्रहीत किए जाते हैं जैसे कि एक मूल नोड में मान अपने दो बच्चों के नोड्स में मूल्यों की तुलना में अधिक (या छोटा) होता है। पूर्व को अधिकतम ढेर कहा जाता है और उत्तरार्द्ध को न्यूनतम ढेर कहा जाता है। ढेर को बाइनरी ट्री या सरणी द्वारा दर्शाया जा सकता है। बाइनरी हीप के लिए सरणी आधारित प्रतिनिधित्व क्यों? चूंकि एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है, इसे आसानी से सरणी के रूप में दर्शाया जा सकता है और सरणी आधारित प्रतिनिधित्व अंतरिक्ष कुशल है। यदि मूल नोड को इंडेक्स I पर संग्रहीत किया जाता है, तो बाएं बच्चे की गणना 2 * I + 1 और दाएं बच्चे द्वारा 2 * I + 2 द्वारा की जा सकती है (मानकर इंडेक्सिंग 0 से शुरू होती है)। हीप का निर्माण कैसे करें? हाइपिफाई प्रक्रिया को नोड पर तभी लागू किया जा सकता है जब उसके बच्चे नोड्स को हटा दें। तो नीचे के क्रम में ढेर का प्रदर्शन किया जाना चाहिए। एक उदाहरण की मदद से समझते हैं: इनपुट डेटा: 4, 10, 3, 5, 1 हीपबनाने की समय जटिलता इनपुट एरे के हीप के निर्माण के लिए निम्नलिखित एल्गोरिथ्म पर विचार करें। निर्माण (ए) हीप: = आकार (ए); मैं के लिए: = मंजिल (ढेर / 2) 1 तक जोर से करो (ए, आई); के लिए अंत समाप्त उपरोक्त एल्गोरिथ्म पर एक त्वरित नज़र बताती है कि रनिंग टाइम O (n lg (n)) है, क्योंकि प्रत्येक कॉल हाइपिफाई की लागत O (lg (n)) और बिल्ड-हीप O (n) ऐसी कॉल करता है। यह ऊपरी बाध्य, हालांकि सही है, स्पर्शोन्मुख रूप से तंग नहीं है। हम यह देखते हुए बाध्य कर सकते हैं कि हाइपिफाई का रनिंग टाइम पेड़ की ऊँचाई 'h' (जो lg (n) के बराबर है, जहाँ n नोड्स की संख्या है) और अधिकांश उप-पेड़ों की ऊँचाई पर निर्भर करता है। छोटे। जैसे ही हम पेड़ के साथ ऊपर की ओर बढ़ते हैं, ऊँचाई 'h' बढ़ जाती है। बिल्ड-हीप की लाइन -3, ऊंचाई = 1 के साथ अंतिम आंतरिक नोड (ढेर / 2) के सूचकांक से एक लूप चलाती है, जड़ के सूचकांक (1) के साथ ऊंचाई = lg (n)। इसलिए, हाइपिफाई प्रत्येक नोड के लिए अलग-अलग समय लेता है, जो O (h) है। एक ढेर के निर्माण की समय जटिलता को खोजने के लिए, हमें पता होना चाहिए कि ऊँचाई वाले नोड्स की संख्या कितनी है। बढ़ते क्रम में छँटाई के लिए हीप सॉर्ट एल्गोरिथ्म: इनपुट डेटा से अधिकतम ढेर बनाएँ। इस बिंदु पर, सबसे बड़ा आइटम ढेर की जड़ में संग्रहीत किया जाता है। 1 के ढेर के आकार को कम करने के बाद ढेर के अंतिम आइटम के साथ बदलें। अंत में, पेड़ की जड़ को ढेर करें। ढेर से ऊपर दोहराएं जबकि ढेर का आकार 1 से अधिक है। दक्षता हीप सॉर्ट एल्गोरिथ्म बहुत कुशल है। जबकि अन्य छँटाई एल्गोरिदम तेजी से वृद्धि कर सकते हैं जैसे कि वस्तुओं की संख्या में वृद्धि हो रही है, हीप छाँटने के लिए आवश्यक समय लघुगणक बढ़ता है। इससे पता चलता है कि ढेर की छँटाई विशेष रूप से वस्तुओं की एक विशाल सूची को छाँटने के लिए उपयुक्त है। इसके अलावा, हीप सॉर्ट का प्रदर्शन इष्टतम है। इसका तात्पर्य यह है कि कोई अन्य छँटाई एल्गोरिदम तुलना में बेहतर प्रदर्शन नहीं कर सकता है। मेमोरी उपयोग हीप सॉर्ट एल्गोरिथ्म को इन-प्लेस सॉर्टिंग एल्गोरिदम के रूप में लागू किया जा सकता है। इसका मतलब यह है कि इसकी मेमोरी का उपयोग कम से कम है क्योंकि इसके अलावा जिन वस्तुओं की सूची को छांटना आवश्यक है, उन्हें काम करने के लिए अतिरिक्त मेमोरी स्पेस की आवश्यकता नहीं है। इसके विपरीत, मर्ज सॉर्ट एल्गोरिथ्म को अधिक मेमोरी स्पेस की आवश्यकता होती है। इसी तरह, क्विक सॉर्ट एल्गोरिथ्म को अपने पुनरावर्ती स्वभाव के कारण अधिक स्टैक स्थान की आवश्यकता होती है। सन्दर्भ इन्हें भी देखें शाटन की कलनविधि (सोर्टिंग अल्गोरिद्म्स) श्रेणी:अल्गोरिद्म श्रेणी:अनुक्रमण सिद्धांत