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

একটি বাইনোমিয়াল হিপ হল বাইনোমিয়াল ট্রি সংগ্রহ। একটি বাইনোমিয়াল ট্রি Bk হল একটি অর্ডারড ট্রি যা রিকার্সিভলি সংজ্ঞায়িত। বাইনোমিয়াল ট্রি B0 একটি একক নোড নিয়ে গঠিত।

একটি বাইনোমিয়াল ট্রি Bk দুটি বাইনোমিয়াল ট্রি Bk-1 নিয়ে গঠিত। সেগুলো একসাথে লিঙ্ক করা থাকে। একটি ট্রির রুট অন্য ট্রির রুটের লেফটমোস্ট চাইল্ড হয়ে যায়।

কিছু বাইনোমিয়াল হিপ নিচের মতো:

বাইনোমিয়াল ট্রির কিছু বৈশিষ্ট্য:

• Bk বাইনোমিয়াল ট্রিতে 2^k নোড থাকে।

• ট্রির উচ্চতা k

• গভীরতা i-তে (0 থেকে k পরিসরে) ঠিক (k choose j) সংখ্যক নোড থাকে।

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

একটি বাইনোমিয়াল হিপ H হল বাইনোমিয়াল ট্রি সংগ্রহ। এর কিছু বৈশিষ্ট্য:

• H-র প্রতিটি বাইনোমিয়াল ট্রি হিপ-অর্ডারড। সুতরাং একটি নোডের কী তার পেরেন্টের কী-র চেয়ে বড় বা সমান।

• H-তে শুধু একটি বাইনোমিয়াল ট্রি থাকতে পারে যার রুটের একটি নির্দিষ্ট ডিগ্রি থাকে।

বাইনোমিয়াল হিপের উদাহরণ

এই বাইনোমিয়াল হিপ H-তে B0, B2 এবং B3 বাইনোমিয়াল ট্রি রয়েছে। যেগুলোর ক্রমশः ১, ৪ এবং ৮টি নোড। মোট n = ১৩ নোড। বাইনোমিয়াল ট্রি-এর রুটগুলো ক্রমবর্ধমান ডিগ্রির ক্রমে একটি লিঙ্কড লিস্ট দ্বারা লিঙ্কড থাকে।