लेख का अनुवाद विशेष रूप से "डेवलपर्स के लिए एल्गोरिदम" पाठ्यक्रम के छात्रों के लिए तैयार किया गया था।

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

बाइनरी हीप क्या है?

आइए पहले एक पूर्ण बाइनरी ट्री को परिभाषित करें। एक समाप्त बाइनरी ट्री एक बाइनरी ट्री है जिसमें प्रत्येक स्तर, अंतिम के संभावित अपवाद के साथ, नोड्स का एक पूरा सेट है, और सभी पत्तियां बाईं ओर स्थित हैं (स्रोत विकिपीडिया )।

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

बाइनरी हीप के लिए सरणी आधारित प्रतिनिधित्व का उपयोग क्यों किया जाता है?

चूंकि बाइनरी हीप एक पूर्ण बाइनरी ट्री है, इसे आसानी से एक सरणी के रूप में दर्शाया जा सकता है, और स्मृति-खपत के संदर्भ में सरणी-आधारित प्रतिनिधित्व कुशल है। यदि मूल नोड अनुक्रमणिका I में संग्रहीत है, तो बाएं बच्चे की गणना 2 I + 1 के रूप में की जा सकती है , और दाएं बच्चे की गणना 2 I + 2 के रूप में की जा सकती है (बशर्ते कि अनुक्रमण 0 से शुरू होता है)।

आरोही क्रम में पिरामिड छँटाई एल्गोरिथ्म:

1. इनपुट से अधिकतम-ढेर बनाएँ।
2. इस स्तर पर, सबसे बड़ा तत्व ढेर की जड़ में जमा होता है। इसे ढेर के अंतिम तत्व के साथ बदलें, और फिर इसके आकार को 1 से कम करें। अंत में, परिणामस्वरूप पेड़ को एक नई जड़ के साथ अधिकतम-ढेर में बदल दें।
3. उपरोक्त चरणों को दोहराएं जब तक कि ढेर का आकार 1 से अधिक न हो।

कैसे एक गुच्छा बनाने के लिए?

हीप रूपांतरण प्रक्रिया (इसके बाद को हीपीफाई प्रक्रिया के रूप में संदर्भित किया जाता है) केवल नोड पर लागू किया जा सकता है यदि उसका बच्चा नोड पहले से ही परिवर्तित हो। इस प्रकार, रूपांतरण नीचे से ऊपर किया जाना चाहिए। आइए इसे एक उदाहरण के साथ समझें:

 : 4, 10, 3, 5, 1 4(0) / \ 10(1) 3(2) / \ 5(3) 1(4)           .   heapify   1: 4(0) / \ 10(1) 3(2) / \ 5(3) 1(4)   heapify   0: 10(0) / \ 5(1) 3(2) / \ 4(3) 1(4)  heapify        . 

सिफारिश: कृपया समाधान के साथ आगे बढ़ने से पहले "समस्या" पर समस्या को हल करें ।

सी ++

 //     C++ #include <iostream> using namespace std; //           i,   //   arr[]. n -   void heapify(int arr[], int n, int i) { int largest = i; //      int l = 2*i + 1; //  = 2*i + 1 int r = 2*i + 2; //  = 2*i + 2 //       if (l < n && arr[l] > arr[largest]) largest = l; //     ,        if (r < n && arr[r] > arr[largest]) largest = r; //       if (largest != i) { swap(arr[i], arr[largest]); //        heapify(arr, n, largest); } } //  ,    void heapSort(int arr[], int n) { //   ( ) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); //        for (int i=n-1; i>=0; i--) { //      swap(arr[0], arr[i]); //   heapify    heapify(arr, i, 0); } } /*         n*/ void printArray(int arr[], int n) { for (int i=0; i<n; ++i) cout << arr[i] << " "; cout << "\n"; } //   int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); heapSort(arr, n); cout << "Sorted array is \n"; printArray(arr, n); } 

जावा

 //     Java public class HeapSort { public void sort(int arr[]) { int n = arr.length; //   ( ) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); //        for (int i=n-1; i>=0; i--) { //      int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; //   heapify    heapify(arr, i, 0); } } //           i,   //   arr[]. n -   void heapify(int arr[], int n, int i) { int largest = i; //      int l = 2*i + 1; //  = 2*i + 1 int r = 2*i + 2; //  = 2*i + 2 //       if (l < n && arr[l] > arr[largest]) largest = l; //     ,        if (r < n && arr[r] > arr[largest]) largest = r; //       if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; //        heapify(arr, n, largest); } } /*         n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); } //   public static void main(String args[]) { int arr[] = {12, 11, 13, 5, 6, 7}; int n = arr.length; HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println("Sorted array is"); printArray(arr); } } 

अजगर

 #     Python #           i,     arr[]. n -   def heapify(arr, n, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 #       ,   if l < n and arr[i] < arr[l]: largest = l #       ,   if r < n and arr[largest] < arr[r]: largest = r #  ,   if largest != i: arr[i],arr[largest] = arr[largest],arr[i] #  #  heapify  . heapify(arr, n, largest) #        def heapSort(arr): n = len(arr) #  max-heap. for i in range(n, -1, -1): heapify(arr, n, i) #      for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] #  heapify(arr, i, 0) #     arr = [ 12, 11, 13, 5, 6, 7] heapSort(arr) n = len(arr) print ("Sorted array is") for i in range(n): print ("%d" %arr[i]), #    Mohit Kumra 

सी तेज

 //     C# using System; public class HeapSort { public void sort(int[] arr) { int n = arr.Length; //   ( ) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); //        for (int i=n-1; i>=0; i--) { //      int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; //   heapify    heapify(arr, i, 0); } } //           i,   //   arr[]. n -   void heapify(int[] arr, int n, int i) { int largest = i; //      int l = 2*i + 1; // left = 2*i + 1 int r = 2*i + 2; // right = 2*i + 2 //       if (l < n && arr[l] > arr[largest]) largest = l; //     ,        if (r < n && arr[r] > arr[largest]) largest = r; //       if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; //        heapify(arr, n, largest); } } /*         n */ static void printArray(int[] arr) { int n = arr.Length; for (int i=0; i<n; ++i) Console.Write(arr[i]+" "); Console.Read(); } //  public static void Main() { int[] arr = {12, 11, 13, 5, 6, 7}; int n = arr.Length; HeapSort ob = new HeapSort(); ob.sort(arr); Console.WriteLine("Sorted array is"); printArray(arr); } } //   // Akanksha Ra (Abby_akku) 

पीएचपी

 <?php //     Php //           i,   //   arr[]. n -   function heapify(&$arr, $n, $i) { $largest = $i; //      $l = 2*$i + 1; //  = 2*i + 1 $r = 2*$i + 2; //  = 2*i + 2 //       if ($l < $n && $arr[$l] > $arr[$largest]) $largest = $l; //    ,        if ($r < $n && $arr[$r] > $arr[$largest]) $largest = $r; //       if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$largest]; $arr[$largest] = $swap; //        heapify($arr, $n, $largest); } } // ,    function heapSort(&$arr, $n) { //   ( ) for ($i = $n / 2 - 1; $i >= 0; $i--) heapify($arr, $n, $i); //       for ($i = $n-1; $i >= 0; $i--) { //      $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; //   heapify    heapify($arr, $i, 0); } } /*         n */ function printArray(&$arr, $n) { for ($i = 0; $i < $n; ++$i) echo ($arr[$i]." ") ; } //   $arr = array(12, 11, 13, 5, 6, 7); $n = sizeof($arr)/sizeof($arr[0]); heapSort($arr, $n); echo 'Sorted array is ' . "\n"; printArray($arr , $n); //    Shivi_Aggarwal ?> 

निष्कर्ष:

  : 5 6 7 11 12 13 

यहाँ संदर्भ के लिए पिछले C कोड है।

टिप्पणी:
पिरामिडिंग छँटाई एक पूरी तरह से उपयुक्त एल्गोरिथ्म है। इसका विशिष्ट कार्यान्वयन स्थिर नहीं है, लेकिन इसे इस प्रकार किया जा सकता है ( यहां देखें)।

समय की जटिलता: हेपिफाइ का समय जटिलता हे (लोगन) है। CreateAndBuildHeap () का समय जटिलता O (n) है, और पिरामिड सॉर्ट का कुल क्रम O (nLogn) है।

पिरामिड क्रमबद्ध अनुप्रयोग:

1. एक लगभग सॉर्ट किया गया (या के पदों द्वारा क्रमबद्ध) सरणी ;
2. k सरणी में सबसे बड़ा (या सबसे छोटा) तत्व ।

पिरामिड सॉर्टिंग एल्गोरिथ्म का सीमित उपयोग है, क्योंकि क्विकॉर्ट और मर्जेसर्ट अभ्यास में बेहतर हैं। हालाँकि, हीप डेटा संरचना ही अक्सर उपयोग किया जाता है। हीप डेटा स्ट्रक्चर एप्लिकेशन देखें

स्क्रीनशॉट:

- (अब जब हमने ढेर का निर्माण किया है, तो हमें इसे अधिकतम-ढेर में बदलने की आवश्यकता है)

- - अधिकतम-ढेर में, मूल नोड हमेशा बच्चे के नोड्स से अधिक या बराबर होता है
10 से अधिक 4. इसलिए, हम 4 और 10 स्वैप करते हैं)
- - अधिकतम-ढेर में, मूल नोड हमेशा बच्चे के नोड्स से अधिक या बराबर होता है
5 अधिक 4. इसलिए, हम 5 और 4 स्थानों को स्वैप करते हैं)

- (पहले और आखिरी नोड्स को स्वैप करें और अंतिम को हीप से हटाएं)

पिरामिड परीक्षण

GeeksforGeeks / GeeksQuiz पर अन्य सॉर्टिंग एल्गोरिदम:
त्वरित सॉर्ट , चयन के आधार पर छाँटें , बबल सॉर्ट , इन्सर्ट सॉर्ट , मर्ज सॉर्ट , पिरामिड सॉर्ट , बिट सॉर्ट , काउंट सॉर्ट , ब्लॉक सॉर्ट , शैल सॉर्ट, कॉम्ब सॉर्ट, काउंट सॉर्ट लिस्ट के साथ ।

छँटाई कार्यशाला

कृपया टिप्पणी छोड़ें यदि आपको कुछ गलत लगता है या आप ऊपर चर्चा किए गए विषय पर अतिरिक्त जानकारी साझा करना चाहते हैं।