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

বাইনোমিয়াল হিপের মতো, ফিবোনাচ্চি হিপও ট্রি সংগ্রহ। এগুলো বাইনোমিয়াল হিপের ওপর ভিত্তি করে তৈরি। কিন্তু বাইনোমিয়াল হিপের ট্রিগুলো অর্ডারড ট্রি, কিন্তু ফিবোনাচ্চি হিপের ট্রিগুলো রুটেড কিন্তু অনঅর্ডারড।

ফিবোনাচ্চি হিপের প্রতিটি নোড x-এ তার পেরেন্টের একটি পয়েন্টার p[x] থাকে, এবং তার চাইল্ডের যেকোনো একটি পয়েন্টার child[x] থাকে। x-এর চাইল্ডগুলো একটি সার্কুলার ডাবলি লিঙ্কড লিস্টে লিঙ্কড থাকে যাকে x-এর চাইল্ড লিস্ট বলা হয়। চাইল্ড লিস্টের প্রতিটি চাইল্ড y-র লেফট[y] এবং রাইট[y] পয়েন্টার থাকে যা y-এর বাম ও ডান সিবলিংকে নির্দেশ করে। যদি নোড y একমাত্র চাইল্ড হয়, তবে left[y] = right[y] = y। চাইল্ড লিস্টে সিবলিংস যাতে আসেন সেটি নির্বিচারে।

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

এই ফিবোনাচ্চি হিপ H পাঁচটি ফিবোনাচ্চি হিপ এবং ১৬টি নোড নিয়ে গঠিত। তীরচিহ্নযুক্ত রেখা রুট লিস্ট নির্দেশ করে। লিস্টে ন্যূনতম নোড min[H]- দ্বারা নির্দেশিত যেটি ৪ ধারণ করছে।

ন্যূনতম স্প্যানিং ট্রি গণনা করা, সিঙ্গেল সোর্স শর্টেস্ট পাথ খুঁজে বের করা ইত্যাদি সমস্যার অ্যাসিম্পটোটিকালি দ্রুত অ্যালগরিদমগুলো ফিবোনাচ্চি হিপের অপরিহার্য ব্যবহার করে।