হিপ অর্ডারিং-এর প্রোপার্টি মেনে চলা কমপ্লিট বাইনারি ট্রিকে বাইনারি হিপ বলা হয়।
বাইনারি হিপের অর্ডারিং এর ওপর ভিত্তি করে এটি দুই ধরনের হতে পারে −
Min Heap হলো এমন হিপ যেখানে নোডের ভ্যালু এর প্যারেন্ট নোডের ভ্যালুর চেয়ে বড় বা সমান হয়। Min heap-এর রুট নোডটি সবচেয়ে ছোট।
Max Heap হলো এমন হিপ যেখানে নোডের ভ্যালু এর প্যারেন্ট নোডের ভ্যালুর চেয়ে ছোট বা সমান হয়। Max heap-এর রুট নোডটি সবচেয়ে বড়।
বাইনারি হিপের মানগুলো সাধারণত একটি অ্যারে-তে রিপ্রেজেন্ট করা হয়। বাইনারি হিপের অ্যারে রিপ্রেজেন্টেশন নিম্নরূপ −
রুট এলিমেন্টের ইনডেক্স ০।
যদি i হয় অ্যারেতে নোডের ইনডেক্স। তবে, সেই নোডের সাথে সম্পর্কিত অন্যান্য নোডগুলো অ্যারেতে ইনডেক্স করা হয় নিম্নরূপ −
Left child: (2*i)+1
Right child: (2*i)+2
Parent child: (i-1)/2
উপরের বাইনারি হিপের অ্যারে রিপ্রেজেন্টেশন নিয়মগুলো ব্যবহার করে আমরা একটি হিপকে অ্যারেতে রিপ্রেজেন্ট করতে পারি −
| 1 | 4 | 7 | 8 | 9 | 11 | 12 |
এখন, অর্ডারিং এর ওপর ভিত্তি করে হিপের টাইপগুলো এখানে আলোচনা করা হলো
Min Heap − রুট নোডে মিনিমাম ভ্যালু থাকে। নোডের ভ্যালু প্যারেন্ট নোডের ভ্যালুর চেয়ে বড়।
উদাহরণ −
অ্যারে রিপ্রেজেন্টেশন −
| 1 | 4 | 7 | 6 | 9 | 10 | 8 |
Max Heap − রুট নোডে ম্যাক্সিমাম ভ্যালু থাকে। নোডের ভ্যালু প্যারেন্ট নোডের ভ্যালুর চেয়ে ছোট।
উদাহরণ −
অ্যারে রিপ্রেজেন্টেশন −
| 11 | 8 | 9 | 6 | 4 | 5 | 1 |
