২২-৫ঃ Heap এ Insertion ইমপ্লিমেন্টেশন

গত মডিউলে আমরা দেখেছি কীভাবে একটি Heap এর internally একটি ভ্যালু insert করে তার থিওরি। এখন দেখবো এদের coding implementation.

প্রথমে দেখে নেয়া যাক , Max Heap এর implementation

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v; //  স্টোর করার জন্য একটি ভেক্টর নেয়া হচ্ছে। 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        v.push_back(x); // একটি ভ্যালু পেলে সেটিকে ভেক্টরের লাস্টে পুশ করে দিলাম। 
       
         // যেহেতু সবার শেষে insert হয়েছে , তাই এর index হবে ভেক্টরের সাইজ হতে ১ কম
        int cur_idx = v.size() - 1; 
        
        // এরপর সেই Node থেকে নিয়ে root পর্যন্ত সব ভ্যালু চেক করা হচ্ছে যতক্ষন parent থেকে children বড় থাকতেছে ততক্ষন 
        
        while (cur_idx != 0) 
        {
            int parent_idx = (cur_idx - 1) / 2; // প্রথমে node টির parent বের করে নেয়া হচ্ছে । 

            // যেহেতু parent সবসময় child থেকে বড় হতে হবে , তাই child এর ভ্যালু বেশি হলে তা parents এর সাথে swap করে ফেলা হচ্ছে।   
            if (v[parent_idx] < v[cur_idx]) ।। 
                swap(v[parent_idx], v[cur_idx]);
            else
                break; // parent বড় হলে আর চেক করার দরকার নেই এখানে ব্রেক হয়ে যাচ্ছে 
            cur_idx = parent_idx; // যদি swap হয় তবে cur index হয়ে যাবে কারণ ভ্যালুটি এখন parent এর প্লেসে চলে গেছে
        }
    }

    for (int val : v)
        cout << val << " ";
    return 0;
}

এরপর Min Heap Implementation

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v; //  স্টোর করার জন্য একটি ভেক্টর নেয়া হচ্ছে। 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        v.push_back(x); // একটি ভ্যালু পেলে সেটিকে ভেক্টরের লাস্টে পুশ করে দিলাম। 
       
         // যেহেতু সবার শেষে insert হয়েছে , তাই এর index হবে ভেক্টরের সাইজ হতে ১ কম
        int cur_idx = v.size() - 1; 
        
        // এরপর সেই Node থেকে নিয়ে root পর্যন্ত সব ভ্যালু চেক করা হচ্ছে যতক্ষন parent থেকে children ছোট থাকতেছে ততক্ষন 
        
        while (cur_idx != 0) 
        {
            int parent_idx = (cur_idx - 1) / 2; // প্রথমে node টির parent বের করে নেয়া হচ্ছে । 

            // যেহেতু parent সবসময় child থেকে ছোট হতে হবে , তাই child এর ভ্যালু ছোট হলে তা parents এর সাথে swap করে ফেলা হচ্ছে।   
            if (v[parent_idx] > v[cur_idx]) ।। 
                swap(v[parent_idx], v[cur_idx]);
            else
                break; // parent ছোট হলে আর চেক করার দরকার নেই এখানে ব্রেক হয়ে যাচ্ছে 
            cur_idx = parent_idx; // যদি swap হয় তবে cur index হয়ে যাবে কারণ ভ্যালুটি এখন parent এর প্লেসে চলে গেছে
        }
    }

    for (int val : v)
        cout << val << " ";
    return 0;
}