২২-৩ঃ Heap কী

Complete Binary Tree শিখে নেয়ার পরে এবার আমরা প্রস্তুত Heap শিখার জন্যে ।

Heap হলো একটি ডাটা স্ট্রাকচার , যার মাধ্যমে আমরা সবসময় একটি container Minimum / maximum ( কোন ধরণের Heap ব্যবহার করছি তার উপর ভিত্তি করে ) ভ্যালুটি বের করে আনতে পারবো ।

Heap দুই ধরনের ।

1. Max Heap : Max Heap এর মাধ্যমে আমরা সবসময় data হতে Maximum ভ্যালুটি বের করে আনতে পারবো। উদাহরণস্বরূপ আমাদের কাছে যদি 10 , 70 , 40 , 5 ,13 এই নাম্বার গুলো একটি Max heap এ স্টোর থাকে তবে ভ্যালু নেয়ার ক্ষেত্রে সর্বপ্রথম 70 পাওয়া যাবে , এরপর 70 নিয়ে নিলে heap এর সবচেয়ে বড় ভ্যালু হবে 40 , 40 নিয়ে নিলে সবচেয়ে বড় ভ্যালু হবে 13 এভাবে করে চলতে থাকবে। অর্থাৎ ঐ মুহূর্তে Heap এ থাকা সবচেয়ে বড় ভ্যালুটি Max Heap রিটার্ন করবে ।

2. Min Heap : MIn Heap এর মাধ্যমে আমরা সবসময় data হতে Minimum ভ্যালুটি বের করে আনতে পারবো। উদাহরণস্বরূপ আমাদের কাছে যদি 10 , 70 , 40 , 5 ,13 এই নাম্বার গুলো একটি Min heap এ স্টোর থাকে তবে ভ্যালু নেয়ার ক্ষেত্রে সর্বপ্রথম 5 পাওয়া যাবে , এরপর 5 নিয়ে নিলে heap এর সবচেয়ে ছোট ভ্যালু হবে 10 , 10 নিয়ে নিলে হবে 13 এভাবে করে চলতে থাকবে। অর্থাৎ ঐ মুহূর্তে Heap এ থাকা সবচেয়ে ছোট ভ্যালুটি Min Heap রিটার্ন করবে ।

দেখে নেয়া যাক , কীভাবে একটি Heap এর স্ট্রাকচার ক্রিয়েট হয় । মনে রাখতে হবে , Heap এর ক্ষেত্রে আমরা কোনো Tree তৈরি করবো না , Array এর মাধ্যমে কাজটি করবো , তবে visual representation এবং কাজের ধরন হবে Complete Binary Tree এর মতো

1. Max Heap এর ক্ষেত্রে প্রত্যেক টা Node এর Child সেই Node থেকে ছোট বা সমান হবে । নিচে একটি Max Heap এর Tree এবং Array representation দেখানো হলো

1. Min Heap এর ক্ষেত্রে প্রত্যেক টা Node এর Child সেই Node থেকে বড় বা সমান হবে । নিচে একটি Min Heap এর Tree এবং Array Representation দেখানো হলো.

Heap আমাদের প্রয়োজন কেনো ?

-> ধরে নিন , আপনার একটি ভেক্টর আছে , সেই ভেক্টরে আপনি নিজের ইচ্ছা মতো ভ্যালু Insert বা Delete করতে পারবেন। এখন আপনি যদি চান , প্রত্যেক ক্ষেত্রে এক্সেস করার সময় আপনি সবচেয়ে বড় ভ্যালুটি এক্সেস করতে চাচ্ছেন , এই ক্ষেত্রে সবচেয়ে বড় ভ্যালুটি Vector এর সবশেষে থাকতে হবে। এখন সবচেয়ে বড় ভ্যালুটি vector এর শেষে রাখতে হলে আমাদের ভেক্টর টি sorted অবস্থায় থাকতে হবে । Nlogn এর সাহায্যে ভেক্টরটি Sort করতে হবে। এরপর আমরা যদি আরেকটা ভ্যালু ঐ ভেক্টরে insert করি তবে সেক্ষেত্রে nlogn এর সাহায্যে আবার sort করতে হবে। যদি N সংখ্যক ভ্যালু insert / delete করি তবে সেক্ষেত্রে N বার Nlogn এর সাহায্যে sort করতে হবে। যা খুবই বেশি time complexity. এক্ষেত্রে Heap এর সাহায্যে কোনো একটি ভ্যালু insert/ delete হলে তা logn কমপ্লেক্সিটি তে sort করা যাবে। এক্ষেত্রে N টি ভ্যালু insert/delete করতে হলে Time complexity লাগবে যা খুব ভালো একটি Time complexity