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

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

फ़ंक्शन विवरण:

• void BHeap::Insert(int ele): हीप में एलिमेंट डालने के लिए इन्सर्शन ऑपरेशन
• void BHeap::DeleteMin(): हीप से न्यूनतम मान हटाने के लिए डिलीशन ऑपरेशन
• int BHeap::ExtractMin(): हीप से न्यूनतम मान निकालने के लिए ऑपरेशन
• void BHeap::showHeap(): हीप के एलिमेंट्स दिखाने के लिए
• void BHeap::heapifyup(int in): बॉटम-अप तरीके से हीप स्ट्रक्चर बनाए रखना
• void BHeap::heapifydown(int in): टॉप-डाउन तरीके से हीप स्ट्रक्चर बनाए रखना

उदाहरण

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

class BHeap {
private:
    vector<int> heap;
    int l(int parent);
    int r(int parent);
    int par(int child);
    void heapifyup(int index);
    void heapifydown(int index);
    
public:
    BHeap() {}
    void Insert(int element);
    void DeleteMin();
    int ExtractMin();
    void showHeap();
    int Size();
};

int main() {
    BHeap h;
    while (1) {
        cout << "1. एलिमेंट डालें" << endl;
        cout << "2. न्यूनतम एलिमेंट हटाएं" << endl;
        cout << "3. न्यूनतम एलिमेंट निकालें" << endl;
        cout << "4. हीप दिखाएं" << endl;
        cout << "5. बाहर निकलें" << endl;
        int c, e;
        cout << "अपनी पसंद दर्ज करें: ";
        cin >> c;
        switch(c) {
            case 1:
                cout << "डालने के लिए एलिमेंट दर्ज करें: ";
                cin >> e;
                h.Insert(e);
                break;
            case 2:
                h.DeleteMin();
                break;
            case 3:
                if (h.ExtractMin() == -1) {
                    cout << "हीप खाली है" << endl;
                } else {
                    cout << "न्यूनतम एलिमेंट: " << h.ExtractMin() << endl;
                }
                break;
            case 4:
                cout << "हीप के एलिमेंट्स दिखा रहे हैं: ";
                h.showHeap();
                break;
            case 5:
                exit(1);
                break;
            default:
                cout << "सही पसंद दर्ज करें" << endl;
        }
    }
    return 0;
}

int BHeap::Size() {
    return heap.size();
}

void BHeap::Insert(int ele) {
    heap.push_back(ele);
    heapifyup(heap.size() - 1);
}

void BHeap::DeleteMin() {
    if (heap.size() == 0) {
        cout << "हीप खाली है" << endl;
        return;
    }
    heap[0] = heap.at(heap.size() - 1);
    heap.pop_back();
    heapifydown(0);
    cout << "एलिमेंट हटाया गया" << endl;
}

int BHeap::ExtractMin() {
    if (heap.size() == 0) {
        return -1;
    }
    return heap.front();
}

void BHeap::showHeap() {
    cout << "हीप --> ";
    for (int val : heap) {
        cout << val << " ";
    }
    cout << endl;
}

int BHeap::l(int parent) {
    int l = 2 * parent + 1;
    if (l < (int)heap.size())
        return l;
    else
        return -1;
}

int BHeap::r(int parent) {
    int r = 2 * parent + 2;
    if (r < (int)heap.size())
        return r;
    else
        return -1;
}

int BHeap::par(int child) {
    int p = (child - 1) / 2;
    if (child == 0)
        return -1;
    else
        return p;
}

void BHeap::heapifyup(int in) {
    if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
        int temp = heap[in];
        heap[in] = heap[par(in)];
        heap[par(in)] = temp;
        heapifyup(par(in));
    }
}

void BHeap::heapifydown(int in) {
    int child = l(in);
    int child1 = r(in);
    if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) {
        child = child1;
    }
    if (child > 0 && heap[in] > heap[child]) {
        int t = heap[in];
        heap[in] = heap[child];
        heap[child] = t;
        heapifydown(child);
    }
}

आउटपुट

1. एलिमेंट डालें
2. न्यूनतम एलिमेंट हटाएं
3. न्यूनतम एलिमेंट निकालें
4. हीप दिखाएं
5. बाहर निकलें
अपनी पसंद दर्ज करें: 1
डालने के लिए एलिमेंट दर्ज करें: 2
...
अपनी पसंद दर्ज करें: 4
हीप के एलिमेंट्स दिखा रहे हैं: हीप --> 2 3 7 6
अपनी पसंद दर्ज करें: 3
न्यूनतम एलिमेंट: 2
अपनी पसंद दर्ज करें: 2
एलिमेंट हटाया गया
अपनी पसंद दर्ज करें: 4
हीप के एलिमेंट्स दिखा रहे हैं: हीप --> 3 6 7

क्लास डिज़ाइन व्याख्या

• इनकैप्सुलेशन: निजी डेटा और हेल्पर फ़ंक्शन्स
• वेक्टर-आधारित: डायनामिक साइज़िंग, ऑटोमैटिक मेमोरी प्रबंधन
• 0-आधारित इंडेक्सिंग: लेफ्ट = 2*i+1, राइट = 2*i+2, पैरेंट = (i-1)/2
• मिन हीप: पैरेंट ≤ चाइल्ड (ExtractMin के लिए)

समय जटिलता

सुधार सुझाव

• टेम्पलेट क्लास बनाएं ताकि किसी भी टाइप के लिए काम करे
• const करेक्टनेस जोड़ें
• कॉपी/मूव सेमांटिक्स इम्प्लीमेंट करें
• std::make_heap, std::push_heap, std::pop_heap का उपयोग करें

STL हीप फ़ंक्शन्स

#include <algorithm>
#include <vector>

vector v = {3, 1, 4, 1, 5, 9};
make_heap(v.begin(), v.end()); // मैक्स हीप बनाता है
push_heap(v.begin(), v.end()); // एलिमेंट जोड़ने के बाद
pop_heap(v.begin(), v.end()); // मैक्स हटाने के बाद
v.pop_back(); // वास्तव में हटाएं
sort_heap(v.begin(), v.end()); // हीप सॉर्ट