C# में हीप सॉर्ट

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

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("हीप सॉर्ट"); 
            Console.Write("प्रारंभिक सरणी है: "); 
            for (i = 0; i < n; i++) { 
                Console.Write(arr[i] + " "); 
            } 
            heapSort(arr, 10); 
            Console.Write("\nक्रमबद्ध सरणी है: "); 
            for (i = 0; i < n; i++) { 
                Console.Write(arr[i] + " "); 
            } 
        } 
    } 
}

आउटपुट

उपरोक्त प्रोग्राम का आउटपुट निम्नलिखित है।

हीप सॉर्ट 
प्रारंभिक सरणी है: 55 25 89 34 12 19 78 95 1 100 
क्रमबद्ध सरणी है: 1 12 19 25 34 55 78 89 95 100

अब, आइए उपरोक्त प्रोग्राम को समझते हैं।

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

int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100}; 
int n = 10, i; 
Console.WriteLine("हीप सॉर्ट"); 
Console.Write("प्रारंभिक सरणी है: "); 
for (i = 0; i < n; i++) { 
    Console.Write(arr[i] + " "); 
} 
heapSort(arr, 10);

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

for (int i = n / 2 - 1; i >= 0; i--) 
    heapify(arr, n, i);

हीप बनने के बाद, हीप के रूट तत्व यानी सबसे बड़े तत्व को हटाने के लिए एक फॉर लूप का उपयोग किया जाता है। इसे सबसे दाएं पत्ते तत्व से बदल दिया जाता है और फिर heapify() को फिर से कॉल करके हीप को पुनर्स्थापित किया जाता है। यह निम्नलिखित कोड स्निपेट में देखा जा सकता है।

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 पर तत्व से शुरू होती है क्योंकि इसे heapify() फ़ंक्शन के लिए रूट तत्व माना जाता है। यह निम्नलिखित कोड स्निपेट में देखा जा सकता है।

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); 
}

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

Console.Write("\nक्रमबद्ध सरणी है: "); 
for (i = 0; i < n; i++) { 
    Console.Write(arr[i] + " "); 
}