বাইনোমিয়াল হিপ (Binomial Heap) C++-এ?

পরিচয়

বাইনোমিয়াল হিপ (Binomial Heap) হলো বাইনারি হিপের একটি এক্সটেনশন যা মার্জ বা ইউনিয়ন অপারেশন দ্রুত করার পাশাপাশি বাইনারি হিপের অন্যান্য অপারেশনও সাপোর্ট করে।

একটি বাইনোমিয়াল হিপকে বাইনোমিয়াল ট্রিয়ের কালেকশন হিসেবে বিবেচনা করা হয়।

বাইনোমিয়াল ট্রি কী?

অর্ডার k-এর একটি বাইনোমিয়াল ট্রি তৈরি করা যায় অর্ডার k-1-এর দুটি বাইনোমিয়াল ট্রি ন लेकर, একটিকে লेफটমост চাইল্ড এবং অন্যটিকে রাইট সিবলিং হিসেবে বিবেচনা করে।

অর্ডার k-এর বাইনোমিয়াল ট্রির বৈশিষ্ট্যগুলো:

• নোড সংখ্যা ঠিক 2^k।
• গভীরতা (depth) k।
• গভীরতা i-তে ঠিক kCi নোড থাকে (i = 0, 1, ..., k)।
• রুটের ডিগ্রি k এবং এর চাইল্ডরা বাম থেকে ডানে অর্ডার k-1, k-2, ..., 0-এর বাইনোমিয়াল ট্রি।

বাইনোমিয়াল হিপ

বাইনোমিয়াল হিপ হলো বাইনোমিয়াল ট্রিয়ের একটি সেট যেখানে প্রতিটি ট্রি মিন-হিপ প্রোপার্টি মেনে চলে। যেকোনো ডিগ্রির জন্য সেটে সেট ডিগ্রির সর্বোচ্চ একটি বাইনোমিয়াল ট্রি থাকতে পারে।

বাইনোমিয়াল হিপের অপারেশনসমূহ

• union() - প্রধান অপারেশন। দুটি বাইনোমিয়াল হিপ মিলিয়ে একটি করে।
• insert(h, K) - কি 'K' হিপ 'h'-তে ইনসার্ট করে। প্রথমে সিঙ্গেল কি দিয়ে একটি হিপ বানায়, তারপর union কল করে।
• getMin(h) - রুট লিস্ট ট্রাভার্স করে স্মalles কি বের করে। O(log n) সময় লাগে। পয়েন্টার মেইনটেইন করলে O(1)-এ করা যায়।
• extractMin(h) - getMin() দিয়ে স্মalles কি বের করে, সেটি রিমুভ করে সাবট্রি গুলো থেকে নতুন হিপ বানায়, তারপর union কল করে। O(log n) সময়।
• delete(h) - কি -infinity করে extractMin() কল করে।
• decreaseKey(h) - কি ডিক্রিজ করে প্যারেন্টের সাথে তুলনা করে সওয়াপ করে। O(log n) সময়।

12 নোড বিশিষ্ট একটি বাইনোমিয়াল হিপ। বাম থেকে ডানে অর্ডার ২ এবং ৩-এর বাইনোমিয়াল ট্রি।

বাইনোমিয়াল হিপ ও বাইনারি রিপ্রেজেন্টেশন

m নোড বিশিষ্ট বাইনোমিয়াল হিপে বাইনোমিয়াল ট্রির সংখ্যা m-এর বাইনারি রিপ্রেজেন্টেশনে সেট বিটের সংখ্যার সমান। উদাহরণ: m=13 (বাইনারি 1101) - ৩টি সেট বিট, তাই ৩টি বাইনোমিয়াল ট্রি। ডিগ্রিগুলো সেট বিটের পজিশনের সাথে সম্পর্কিত। তাই m নোডের হিপে O(log m) বাইনোমিয়াল ট্রি থাকে।