सी # में ढेर क्रमबद्ध करें

हीप सॉर्ट एक सॉर्टिंग एल्गोरिथम है जो हीप डेटा संरचना का उपयोग करता है। हर बार हीप का मूल तत्व यानी सबसे बड़ा तत्व हटा दिया जाता है और एक सरणी में संग्रहीत किया जाता है। इसे सबसे दाहिने पत्ते के तत्व से बदल दिया जाता है और फिर ढेर को फिर से स्थापित किया जाता है। यह तब तक किया जाता है जब तक कि ढेर में कोई और तत्व नहीं बचे हैं और सरणी को क्रमबद्ध किया जाता है।

एक प्रोग्राम जो C# में हीप सॉर्ट प्रदर्शित करता है, वह इस प्रकार दिया गया है।

उदाहरण

using System;
namespace HeapSortDemo {
   public class example {
      static 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--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
         }
      }
      static void heapify(int[] arr, int n, int i) {
         int largest = i;
         int left = 2*i + 1;
         int right = 2*i + 2;
         if (left < n && arr[left] > arr[largest])
         largest = left;
         if (right < n && arr[right] > arr[largest])
         largest = right;
         if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
         }
      }
      public static void Main() {
         int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
         int n = 10, i;
         Console.WriteLine("Heap Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         heapSort(arr, 10);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

आउटपुट

उपरोक्त कार्यक्रम का आउटपुट इस प्रकार है।

Heap Sort
Initial array is: 55 25 89 34 12 19 78 95 1 100
Sorted Array is: 1 12 19 25 34 55 78 89 95 100

अब, उपरोक्त कार्यक्रम को समझते हैं।

फ़ंक्शन मुख्य () में सरणी गिरफ्तारी होती है। यह प्रारंभिक सरणी को प्रिंट करता है और फिर फ़ंक्शन को कॉल करता है heapSort() जो सरणी को सॉर्ट करेगा। इसे निम्नलिखित कोड स्निपेट में देखा जा सकता है।

int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
heapSort(arr, 10);

फ़ंक्शन heapSort () पहले दिए गए तत्वों को एक ढेर में परिवर्तित करता है। यह लूप के लिए उपयोग करके और हीप के सभी गैर-पत्ती तत्वों के लिए फ़ंक्शन को कॉल करके किया जाता है। इसे निम्नलिखित कोड स्निपेट में देखा जा सकता है।

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(arr, i, 0);
}

फ़ंक्शन heapify () आवश्यकतानुसार तत्वों को व्यवस्थित करके एक ढेर संरचना बनाता है। यह प्रक्रिया इंडेक्स i के एलिमेंट से शुरू होती है, इसके लिए हेपिफाई () फंक्शन के लिए रूट एलिमेंट माना जाता है। इसे निम्नलिखित कोड स्निपेट में देखा जा सकता है।

int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
   int swap = arr[i];
   arr[i] = arr[largest];
   arr[largest] = swap;
   heapify(arr, n, largest);
}

अंत में, क्रमबद्ध सरणी मुख्य () फ़ंक्शन में प्रदर्शित होती है। इसे निम्नलिखित कोड स्निपेट में देखा जा सकता है।

Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}