heap sort c with examples
उदाहरणों के साथ छाँटने का एक परिचय।
हीपसॉर्ट सबसे कुशल छँटाई तकनीकों में से एक है। यह तकनीक दिए गए अनसोल्ड एरे से ढेर बनाती है और फिर एरे को सॉर्ट करने के लिए फिर से हीप का इस्तेमाल करती है।
हीप्सोर्ट एक छँटाई तकनीक है जो तुलना पर आधारित है और बाइनरी हीप का उपयोग करता है।
=> आसान सी ++ प्रशिक्षण श्रृंखला के माध्यम से पढ़ें।
एक राउटर पर नेटवर्क सुरक्षा कुंजी क्या है
आप क्या सीखेंगे:
बाइनरी हीप क्या है?
एक बाइनरी हीप को एक पूर्ण बाइनरी ट्री का उपयोग करके दर्शाया गया है। एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है, जिसमें प्रत्येक स्तर पर सभी नोड्स पत्ती नोड्स को छोड़कर पूरी तरह से भरे हुए हैं और नोड्स अभी तक बचे हुए हैं।
एक बाइनरी हीप या बस एक हीप एक पूर्ण बाइनरी ट्री है जहां आइटम या नोड्स को इस तरह से संग्रहीत किया जाता है कि रूट नोड उसके दो बच्चे नोड्स से अधिक हो। इसे अधिकतम ढेर भी कहा जाता है।
बाइनरी हीप में आइटम को मिन-हीप के रूप में भी संग्रहीत किया जा सकता है, जिसमें रूट नोड अपने दो बच्चे नोड्स से छोटा है। हम एक बाइनरी ट्री या एक सरणी के रूप में एक ढेर का प्रतिनिधित्व कर सकते हैं।
एक सरणी के रूप में एक ढेर का प्रतिनिधित्व करते हुए, यह मानते हुए कि सूचकांक 0 से शुरू होता है, मूल तत्व 0 पर संग्रहीत होता है। सामान्य तौर पर, यदि कोई अभिभावक नोड I की स्थिति पर है, तो बाएं बच्चे का नोड स्थिति में है (2 * I + 1) और सही नोड है (2 * I +2)।
सामान्य एल्गोरिथम
नीचे दिए गए ढेर सॉर्ट तकनीक के लिए सामान्य एल्गोरिदम है।
- दिए गए डेटा से अधिकतम ढेर का निर्माण करें जैसे कि जड़ हीप का उच्चतम तत्व है।
- जड़ को हटा दें यानी ढेर से उच्चतम तत्व और इसे ढेर के अंतिम तत्व से बदल दें या स्वैप करें।
- फिर अधिकतम हीप को समायोजित करें, ताकि अधिकतम हीप गुणों (हीइफीफाय) का उल्लंघन न करें।
- उपरोक्त चरण 1 से ढेर के आकार को कम करता है।
- उपरोक्त तीन चरणों को दोहराएं जब तक कि ढेर का आकार 1 तक कम न हो जाए।
जैसा कि बढ़ते हुए क्रम में दिए गए डेटासेट को सॉर्ट करने के लिए सामान्य एल्गोरिथम में दिखाया गया है, हम पहले दिए गए डेटा के लिए अधिकतम ढेर का निर्माण करते हैं।
आइए हम निम्नलिखित डेटासेट के साथ अधिकतम ढेर बनाने के लिए एक उदाहरण लेते हैं।
6, 10, 2, 4, 1
हम इस डेटा सेट के लिए एक पेड़ का निर्माण इस प्रकार कर सकते हैं।
ऊपर के पेड़ के प्रतिनिधित्व में, कोष्ठक में संख्याएँ सरणी में संबंधित पदों का प्रतिनिधित्व करती हैं।
उपरोक्त प्रतिनिधित्व के अधिकतम ढेर का निर्माण करने के लिए, हमें ढेर स्थिति को पूरा करने की आवश्यकता है कि मूल नोड अपने बच्चे के नोड्स से अधिक होना चाहिए। दूसरे शब्दों में, हमें पेड़ को 'ढेर' करने की आवश्यकता है ताकि इसे अधिकतम-ढेर में परिवर्तित किया जा सके।
उपरोक्त पेड़ के ढेर लगाने के बाद, हम नीचे दिखाए गए अनुसार अधिकतम-ढेर प्राप्त करेंगे।
जैसा कि ऊपर दिखाया गया है, हमारे पास एक सरणी से उत्पन्न यह अधिकतम-ढेर है।
अगला, हम ढेर प्रकार का एक चित्रण प्रस्तुत करते हैं। मैक्स-हीप के निर्माण को देखने के बाद, हम मैक्स-हीप के निर्माण के लिए विस्तृत चरणों को छोड़ देंगे और प्रत्येक चरण पर अधिकतम हीप को सीधे दिखाएंगे।
चित्रण
तत्वों की निम्नलिखित सरणी पर विचार करें। हमें इस प्रकार को ढेर सॉर्ट तकनीक का उपयोग करके सॉर्ट करना होगा।
हमें एक अधिकतम ढेर का निर्माण करना चाहिए जैसा कि सरणी को क्रमबद्ध करने के लिए नीचे दिखाया गया है।
एक बार ढेर का निर्माण हो जाने के बाद, हम नीचे दिखाए गए अनुसार इसे Array रूप में दर्शाते हैं।
अब हम 1 की तुलना करते हैंअनुसूचित जनजातिपिछले नोड के साथ नोड (रूट) और फिर उन्हें स्वैप करें। इस प्रकार, जैसा कि ऊपर दिखाया गया है, हम 17 और 3 स्वैप करते हैं ताकि 17 अंतिम स्थान पर हो और 3 पहले स्थान पर हो।
अब हम ढेर से नोड 17 को हटाते हैं और इसे सॉर्ट किए गए सरणी में डालते हैं जैसा कि नीचे छायांकित भाग में दिखाया गया है।
अब हम फिर से एरे तत्वों के लिए एक ढेर का निर्माण करते हैं। इस बार ढेर का आकार 1 से कम हो गया है क्योंकि हमने एक तत्व (17) को ढेर से हटा दिया है।
शेष तत्वों का ढेर नीचे दिखाया गया है।
अगले चरण में, हम उसी चरणों को दोहराएंगे।
हम मूल तत्व और अंतिम तत्व को ढेर में तुलना और स्वैप करते हैं।
स्वैप करने के बाद, हम तत्व 12 को हीप से हटाते हैं और इसे सॉर्ट किए गए ऐरे में शिफ्ट करते हैं।
एक बार फिर हम शेष तत्वों के लिए एक अधिकतम ढेर का निर्माण करते हैं जैसा कि नीचे दिखाया गया है।
अब हम रूट और लास्ट एलिमेंट यानी 9 और 3. को स्वैप करते हैं। स्वैप करने के बाद, एलीमेंट 9 को हीप से डिलीट कर सॉर्ट की गई एरे में डाल दिया जाता है।
इस बिंदु पर, हमारे पास केवल तीन तत्व हैं जो नीचे दिखाए गए हैं।
हम 6 और 3 स्वैप करते हैं और तत्व 6 को ढेर से हटाते हैं और इसे सॉर्ट किए गए सरणी में जोड़ते हैं।
अब हम शेष तत्वों के ढेर का निर्माण करते हैं और फिर दोनों को एक दूसरे के साथ स्वैप करते हैं।
20 से अधिक मिनट तक यूट्यूब
4 और 3 को स्वैप करने के बाद, हम तत्व 4 को हीप से हटाते हैं और इसे सॉर्ट किए गए ऐरे में जोड़ते हैं। अब हमारे पास केवल एक नोड शेष में शेष है जैसा कि नीचे दिखाया गया है ।
तो अब केवल एक नोड शेष है, हम इसे ढेर से हटाते हैं और इसे सॉर्ट किए गए सरणी में जोड़ते हैं।
इस प्रकार ऊपर दिखाया गया क्रमबद्ध सरणी है जिसे हमने ढेर के प्रकार के परिणामस्वरूप प्राप्त किया है।
उपर्युक्त दृष्टांत में, हमने आरोही क्रम में क्रमबद्ध किया है। यदि हमें सरणी को अवरोही क्रम में क्रमबद्ध करना है तो हमें उसी चरणों का पालन करने की आवश्यकता है लेकिन न्यूनतम-ढेर के साथ।
हीप्सर्ट एल्गोरिथ्म चयन प्रकार के समान है जिसमें हम सबसे छोटे तत्व का चयन करते हैं और इसे क्रमबद्ध सरणी में रखते हैं। हालाँकि, जहाँ तक प्रदर्शन की बात है, चयन प्रकार की तुलना में हीप छँटाई अधिक तेज़ है। हम इसे डाल सकते हैं क्योंकि हीप्सॉर्ट चयन प्रकार का एक बेहतर संस्करण है।
अगला, हम C + और जावा भाषा में हीप्सोर्ट को लागू करेंगे।
दोनों कार्यान्वयन में सबसे महत्वपूर्ण कार्य 'heapify' फ़ंक्शन है। यह फ़ंक्शन मुख्य नोड्स रूटीन द्वारा बुलाया जाता है ताकि एक नोड को हटाए जाने पर या अधिकतम-हीप निर्मित होने पर सबट्री को फिर से व्यवस्थित किया जा सके।
जब हमने पेड़ को सही ढंग से ठीक किया है, तभी हम उनकी सही स्थिति में सही तत्व प्राप्त कर पाएंगे और इस तरह से सरणी को सही ढंग से हल किया जाएगा।
C ++ उदाहरण
हाइपोसॉर्ट कार्यान्वयन के लिए C ++ कोड निम्नलिखित है।
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i आउटपुट:
इनपुट सरणी
४ १ 4 ३ १२ ९ ६
क्रमबद्ध सरणी
३ ४ ६ ९ १२ १ 17
अगला, हम जावा भाषा में हीप्सोर्ट को लागू करेंगे
जावा उदाहरण
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i आउटपुट:
विंडोज़ 7 में बिन फ़ाइल कैसे खोलें
इनपुट सरणी:
४ १ 4 ३ १२ ९ ६
क्रमबद्ध सरणी:
३ ४ ६ ९ १२ १ 17
निष्कर्ष
हीप्सोर्ट बाइनरी हीप का उपयोग करते हुए एक तुलना आधारित सॉर्टिंग तकनीक है।
इसे चयन प्रकार पर सुधार के रूप में कहा जा सकता है क्योंकि ये दोनों छंटाई तकनीक बार-बार सरणी में सबसे बड़े या सबसे छोटे तत्व को खोजने और फिर इसे क्रमबद्ध सरणी में रखने के समान तर्क के साथ काम करते हैं।
हीप सॉर्ट सरणी को सॉर्ट करने के लिए मैक्स-हीप या मिन-हीप का उपयोग करता है। हीप सॉर्ट में पहला कदम सरणी डेटा से एक मिनट या अधिकतम हीप का निर्माण करना है और फिर रूट तत्व को पुनरावर्ती रूप से हटाना और ढेर को ढेर करना है जब तक कि ढेर में केवल एक नोड मौजूद न हो।
हीप्सोर्ट एक कुशल एल्गोरिथ्म है और यह चयन प्रकार की तुलना में तेजी से प्रदर्शन करता है। इसका उपयोग लगभग सॉर्ट किए गए सरणी को सॉर्ट करने या सरणी में सबसे बड़ा या सबसे छोटा तत्व खोजने के लिए किया जा सकता है।
इसके साथ, हमने C ++ में तकनीकों को छाँटने पर अपना विषय पूरा कर लिया है। अपने अगले ट्यूटोरियल से, हम एक-एक करके डेटा संरचनाओं के साथ शुरू करेंगे।
=> संपूर्ण सी ++ प्रशिक्षण श्रृंखला यहां देखें।
अनुशंसित पाठ
- MongoDB सॉर्ट () उदाहरणों के साथ विधि
- सिंटेक्स, विकल्प और उदाहरण के साथ यूनिक्स सॉर्ट कमांड
- उदाहरणों के साथ C ++ में मर्ज करें
- शैल C ++ में उदाहरणों के साथ
- उदाहरणों के साथ C ++ में प्रविष्टि सॉर्ट करें
- चयन सी में सी ++ उदाहरण के साथ
- उदाहरणों के साथ C ++ में बबल सॉर्ट
- उदाहरण के साथ C ++ में त्वरित क्रमबद्ध