ডেটা স্ট্রাকচারে ফিবোনাচি হিপস

দ্বিপদ স্তুপের মতো, ফিবোনাচি স্তূপগুলি হল গাছের সংগ্রহ৷ তারা আলগাভাবে দ্বিপদ স্তূপ উপর ভিত্তি করে. দ্বিপদী স্তূপযুক্ত গাছের বিপরীতে ফিবোনাচির স্তূপের মধ্যে গাছগুলিকে রুট করা হয় তবে ক্রমবিন্যস্ত করা হয়৷

ফিবোনাচি হিপসের প্রতিটি নোড x-এ তার পিতামাতার জন্য একটি পয়েন্টার p[x] এবং তার সন্তানদের একজনের জন্য একটি পয়েন্টার চাইল্ড[x] থাকে। x-এর বাচ্চাদের একটি বৃত্তাকার দ্বিগুণ লিঙ্কযুক্ত তালিকায় একসাথে যুক্ত করা হয় যা x-এর চাইল্ড লিস্ট নামে পরিচিত। চাইল্ড লিস্টের প্রতিটি শিশু y এর বাম এবং ডান ভাইবোনদের যথাক্রমে y এর বাম এবং ডানদিকে নির্দেশ করার জন্য পয়েন্টার রয়েছে। যদি নোড y শুধুমাত্র শিশু হয় তাহলে left[y] =right[y] =y। একটি শিশু তালিকায় ভাইবোন যে ক্রমানুসারে উপস্থিত হয় তা স্বেচ্ছাচারী৷

ফিবোনাচি হিপের উদাহরণ

এই Fibonacci Heap H পাঁচটি Fibonacci Heaps এবং 16 নোড নিয়ে গঠিত। তীর মাথার লাইনটি মূল তালিকা নির্দেশ করে। তালিকার সর্বনিম্ন নোডকে min[H] দ্বারা চিহ্নিত করা হয় যা 4 ধারণ করে।

ন্যূনতম বিস্তৃত গাছ গণনা করা, সংক্ষিপ্ততম পথের একক উৎস খুঁজে বের করা ইত্যাদি সমস্যাগুলির জন্য অ্যাসিম্পটোটিকভাবে দ্রুত অ্যালগরিদমগুলি ফিবোনাচি হিপসের অপরিহার্য ব্যবহার করে৷