C++ प्रोग्राम: मिन हीप इम्प्लीमेंटेशन

एक बाइनरी हीप एक पूर्ण बाइनरी ट्री है जो या तो मिन हीप या मैक्स हीप होता है। एक मैक्स बाइनरी हीप में, रूट पर की हीप में मौजूद सभी कीज़ में अधिकतम होनी चाहिए। यह गुण बाइनरी ट्री में सभी नोड्स के लिए रिकर्सिवली सत्य होना चाहिए। मिन बाइनरी हीप मिन हीप के समान है।

एल्गोरिदम

min_heap() के लिए:

शुरुआत
    फ़ंक्शन min_heap(int* a, int m, int n) घोषित करें
    j, t को integer डेटाटाइप घोषित करें
    t = a[m] इनिशियलाइज़ करें
    j = 2 * m
    while (j <= n) करें
        if (j < n और a[j+1] < a[j]) तो
            j = j + 1
        if (t < a[j]) तो
            ब्रेक
        else if (t >= a[j]) तो
            a[j / 2] = a[j]
            j = 2 * j
    a[j/2] = t
    लौटाएं
समाप्ति

build_minheap के लिए:

शुरुआत
    फ़ंक्शन build_minheap(int* a, int n) घोषित करें
    k को integer डेटाटाइप घोषित करें
    for(k = n/2; k >= 1; k--)
        फ़ंक्शन min_heap(a, k, n) कॉल करें
समाप्ति

उदाहरण

#include <iostream>
#include <vector>
using namespace std;

void min_heap(vector& a, int m, int n) {
    int j, t;
    t = a[m];
    j = 2 * m;
    while (j <= n) {
        if (j < n && a[j+1] < a[j])
            j = j + 1;
        if (t < a[j])
            break;
        else if (t >= a[j]) {
            a[j/2] = a[j];
            j = 2 * j;
        }
    }
    a[j/2] = t;
}

void build_minheap(vector& a, int n) {
    for (int k = n/2; k >= 1; k--) {
        min_heap(a, k, n);
    }
}

int main() {
    int n;
    cout << "ऐरे के एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    vector a(n + 1); // 1-आधारित इंडेक्सिंग
    
    for (int i = 1; i <= n; i++) {
        cout << "एलिमेंट " << i << " दर्ज करें: ";
        cin >> a[i];
    }
    
    build_minheap(a, n);
    cout << "मिन हीप:\n";
    for (int i = 1; i <= n; i++) {
        cout << a[i] << endl;
    }
    return 0;
}

आउटपुट

ऐरे के एलिमेंट्स की संख्या दर्ज करें: 5
एलिमेंट 1 दर्ज करें: 7
एलिमेंट 2 दर्ज करें: 6
एलिमेंट 3 दर्ज करें: 2
एलिमेंट 4 दर्ज करें: 1
एलिमेंट 5 दर्ज करें: 4
मिन हीप:
1
4
2
6
7

आधुनिक C++: std::priority_queue (मिन हीप)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // मिन हीप (डिफ़ॉल्ट मैक्स हीप है, इसलिए greater उपयोग करें)
    priority_queue, greater> minHeap;
    
    minHeap.push(7);
    minHeap.push(6);
    minHeap.push(2);
    minHeap.push(1);
    minHeap.push(4);
    
    cout << "मिन हीप एलिमेंट्स (सॉर्टेड क्रम में): ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;
    
    return 0;
}

आउटपुट

मिन हीप एलिमेंट्स (सॉर्टेड क्रम में): 1 2 4 6 7

हीप ऑपरेशन्स जटिलता

मूल कोड में सुधार

• conio.h और getch() हटाए गए (नॉन-स्टैंडर्ड)
• vector का उपयोग किया गया फिक्स्ड ऐरे के बजाय
• 0-आधारित इंडेक्सिंग के लिए समायोजित (मूल 1-आधारित था)
• बेहतर मेमोरी प्रबंधन