हीप सॉर्ट

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

हीप सॉर्ट तकनीक की जटिलता

• टाइम कॉम्प्लेक्सिटी: O(n log n)
• स्पेस कॉम्प्लेक्सिटी: O(1)

इनपुट और आउटपुट

इनपुट: अनसॉर्टेड डेटा की लिस्ट: 30 8 99 11 24 39
आउटपुट: सॉर्टिंग से पहले ऐरे: 30 8 99 11 24 39
सॉर्टिंग के बाद ऐरे: 8 11 24 30 39 99

एल्गोरिदम

heapify(array, size)

इनपुट: डेटा का एक ऐरे, और ऐरे में कुल संख्या

आउटपुट: ऐरे एलिमेंट का उपयोग करके मैक्स हीप

Begin
    for i := 1 to size do
        node := i
        par := floor(node / 2)
        while par >= 1 do
            if array[par] < array[node] then
                swap array[par] with array[node]
            node := par
            par := floor(node / 2)
        done
    done
End

heapSort(array, size)

इनपुट: डेटा का एक ऐरे, और ऐरे में कुल संख्या

आउटपुट: सॉर्टेड ऐरे

Begin
    for i := n to 1 decrease by 1 do
        heapify(array, i)
        swap array[1] with array[i]
    done
End

उदाहरण

#include <iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 1; i <= size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void heapify(int *array, int n) {
    int i, par, l, r, node;
    // मैक्स हीप बनाएं
    for(i = 1; i <= n; i++) {
        node = i; par = (int)node / 2;
        while(par >= 1) {
            // यदि नया नोड पैरेंट से बड़ा है, तो स्वैप करें
            if(array[par] < array[node])
                swap(array[par], array[node]);
            node = par;
            par = (int)node / 2; // चेक करने के लिए पैरेंट अपडेट करें
        }
    }
}

void heapSort(int *array, int n) {
    int i;
    for(i = n; i >= 1; i--) {
        heapify(array, i); // हर बार हीपिफाई करें
        swap(array[1], array[i]); // लास्ट एलिमेंट को पहले के साथ स्वैप करें
    }
}

int main() {
    int n;
    cout << "एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    int arr[n + 1]; // प्रभावी इंडेक्स i = 1 से शुरू होता है
    cout << "एलिमेंट्स दर्ज करें:" << endl;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    cout << "सॉर्टिंग से पहले ऐरे: ";
    display(arr, n);
    heapSort(arr, n);
    cout << "सॉर्टिंग के बाद ऐरे: ";
    display(arr, n);
}

आउटपुट

एलिमेंट्स की संख्या दर्ज करें: 6
एलिमेंट्स दर्ज करें: 30 8 99 11 24 39
सॉर्टिंग से पहले ऐरे: 30 8 99 11 24 39
सॉर्टिंग के बाद ऐरे: 8 11 24 30 39 99