২২-৬ঃ Heap এ Deletion থিওরি

Heap এ Insertion এর মতো deletion এর প্রসেসটিও প্রায় একই। সবক্ষেত্রেই আমাদের Heap এর rules মেনে চলতে হবে ।

Heap একটি নির্দিষ্ট স্ট্রাকচার ফলো করে তা হলো Max Heap এ ট্রি এর প্রত্যেক টি Node এর child হতে সেই Node বড় হতে হবে। প্রত্যেক ক্ষেত্রে এই স্ট্রাকচার টি মেইনটেইন করেই আমরা Heap এ Deletion করতে পারবো ।

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

এখন আমরা একটি ভ্যালু এই Heap থেকে delete করবো । Delete করার সময় আমরা জানি , Max Heap এর ক্ষেত্রে সবচেয়ে বড় ভ্যালুটি Delete হবে যা Root এ অবস্থান করে। নিচে স্টেপ গুলো নিয়ে আলোচনা করা হলো। ১। যেহেতু একটি ডাইনামিক Array অর্থাৎ Vector এর সাহায্যে কাজটি করা হয় তাই deletion এর ক্ষেত্রে vector এর শেষে ভ্যালুটি O(1) কমপ্লেক্সিটি তে deletion করা যাবে। এক্ষেত্রে প্রথমে আমরা শেষ ভ্যালুটির সাথে Root এর ভ্যালুটি swap করবো । এবং ভেক্টরের শেষের index টি delete করে দিবো।

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

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