C++ প্রোগ্রাম: বাইনারি হিপ (Binary Heap) বাস্তবায়ন

বাইনারি হিপ (Binary Heap) একটি কমপ্লিট বাইনারি ট্রি যা মিন হিপ (Min Heap) বা ম্যাক্স হিপ (Max Heap) হতে পারে। ম্যাক্স বাইনারি হিপে রুটের কী সকল কীতে চেয়ে বড় হতে হবে। এই প্রপার্টি রিকারসিভলি সব নোডের জন্য সত্য হতে হবে। মিন বাইনারি হিপও সমানrules মেনে চলে।

ফাংশন বিবরণ

• 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 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.Insert Element\n2.Delete Minimum Element\n3.Extract Minimum Element\n4.Show Heap\n5.Exit\nEnter your choice: ";
        int c, e; cin >> c;
        switch(c) {
            case 1:
                cout << "Enter the element to be inserted: "; cin >> e;
                h.Insert(e); break;
            case 2: h.DeleteMin(); break;
            case 3:
                if (h.ExtractMin() == -1) cout << "Heap is Empty\n";
                else cout << "Minimum Element: " << h.ExtractMin() << endl;
                break;
            case 4:
                cout << "Displaying elements of Heap: "; h.showHeap(); break;
            case 5: exit(1);
            default: cout << "Enter Correct Choice\n";
        }
    }
    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 << "Heap is Empty\n"; return; }
    heap[0] = heap.at(heap.size() - 1);
    heap.pop_back();
    heapifydown(0);
    cout << "Element Deleted\n";
}

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

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

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

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

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

void BHeap::heapifyup(int in) {
    if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
        swap(heap[in], heap[par(in)]);
        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]) {
        swap(heap[in], heap[child]);
        heapifydown(child);
    }
}

আউটপুট (নমুনা)

1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 2
...
Displaying elements of Heap: Heap --> 2 3 7 6
Minimum Element: 2
Element Deleted
Displaying elements of Heap: Heap --> 3 6 7
...