২২-৪ঃ Heap এ Insertion এর থিওরি

Heap এ insert করার থিওরি খুব ই সিম্পল এবং বেসিক । Heap একটি নির্দিষ্ট স্ট্রাকচার ফলো করে তা হলো Max Heap এ ট্রি এর প্রত্যেক টি Node এর child হতে সেই Node বড় হতে হবে। প্রত্যেক ক্ষেত্রে এই স্ট্রাকচার টি মেইনটেইন করেই আমরা Heap এ Insertion করতে পারবো ।

Heap এ Insertion করার নিয়মঃ 1. ভেক্টরের শেষে ভ্যালু Add করা। 2. যতক্ষন পর্যন্ত Heap এর রুলস ফলো হচ্ছে না ততক্ষন পর্যন্ত ঐ Node কে তার Parent এর সাথে কম্পেয়ার করে swap করতে থাকা। ধরে নিই আমাদের নিন্মের চিত্রের এই Heap টি দেয়া আছে।

এখন আমরা একটি ভ্যালু 60এই Heap এ insert করবো । নিচে স্টেপ গুলো নিয়ে আলোচনা করা হলো। ১। যেহেতু একটি ডাইনামিক Array অর্থাৎ Vector এর সাহায্যে কাজটি করা হয় তাই Insertion এর ক্ষেত্রে vector এর শেষে ভ্যালুটি O(1) কমপ্লেক্সিটি তে insertion করা যাবে।

২। শেষে Insertion করার পর দেখা গেলো একটি Max Heap এর স্ট্রাকচার এর Rules যেটি আছে সেটি ব্রেক করেছে । আমরা যদি ২ নাম্বার Node কে খেয়াল করি তবে দেখা যায় 2 নাম্বার Node এ ভ্যালু আছে 45 এবং 2 নাম্বার Node এর right children 6 নাম্বার Node এ ভ্যালু আছে 60. কিন্তু Max Heap এর স্ট্রাকচার অনুযায়ী Parent সবসময় বড় হতে হবে। এখন আমরা ভ্যালু গুলো swap করার মাধ্যমে এই স্ট্রাকচার টি আবার ফিরিয়ে আনার চেষ্টা করবো। তাই 6 এর parent , 2 নাম্বার Node এর সাথে ভ্যালুটি swap করা হলো

৩। swap করার পর 2 নাম্বার Node এর জন্য Heap এর স্ট্রাকচার টি ঠিক হলো। কিন্তু overall দেখলে Heap টি এখনো কাঙ্খিত structure টির recquirement মিট করছে না। আমরা যদি 0 নাম্বার Node কে খেয়াল করি তবে দেখা যায় 0 নাম্বার Node এ ভ্যালু আছে 50 এবং 0 নাম্বার Node এর right children 2 নাম্বার Node এ ভ্যালু আছে 60. কিন্তু Max Heap এর স্ট্রাকচার অনুযায়ী Parent সবসময় বড় হতে হবে। এখন আমরা ভ্যালু গুলো swap করার মাধ্যমে এই স্ট্রাকচার টি আবার ফিরিয়ে আনার চেষ্টা করবো। তাই 2 এর parent , 0 নাম্বার Node এর সাথে ভ্যালুটি swap করা হলো

এবং সবশেষে Heap এর কাঙ্খিত স্ট্রাকচারটি পাওয়া গেলো এবং কাজ টি এখানে থেমে যাবে। টাইম কমপ্লেক্সিটিঃ আমরা জানি একটি Complete Binary Tree এর Max Height হলো logN. এখানে যেহেতু একটি Node insertion করার পর , তা root পর্যন্ত তার parent এর সাথে চেক করে swap করতে থাকে , এই ক্ষেত্রে একটি Node ম্যাক্সিমাম তার height বরাবর উপরের দিকে উঠতে থাকে এবং চেক করতে থাকে। যা তার height logN এর সমান , এখানে N হলো Heap এর Node সংখ্যা। তাই Heap এ insertion এর টাইম কমপ্লেক্সিটি O(logN). Min Heap এর Insertion এর কাজটি একই , শুধুমাত্র structure এর কন্ডিশন এ একটু ভিন্নতা আছে। যা আমরা code সেকশনে আলোচনা করবো।