موضوع مقاله: هرم فیبوناچی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # هرم فیبوناچی | مقدمه: در علوم کامپیوتر، هیپ فیبوناتچی به داده ساختار هیپی گفته می‌شود که شامل انبوهی از درخت‌ها است. | ## بخش 1: هرم فیبوناچی | هیپ‌های فیبوناتچی توسط مایکل فردمن و رابرت تارجن در سال ۱۹۸۴ ایجاد شده‌اند، و برای اولین بار در یک مقاله علمی در سال ۱۹۸۷ منتشر شدند. ایده نام هیپ فیبوناتچی از اعداد فیبوناتچی که در اجرای تحلیل زمانی از آن استفاده می‌شود، گرفته شده‌است. اعمال درج، یافتن کوچکترین مقدار، کاهش کلید، و ادغام (الحاق) در زمان سرشکن ثابت کار می‌کنند. این بدین معناست که با شروع از یک داده ساختار خالی، a عمل از دستورها گروه اول و b عمل از دستورها گروه دوم، زمان اجرای خواهد داشت. در هیپ‌های دو جمله انجام چنین عملی نیاز به زمان اجرای دارد؛ بنابراین زمانی که b از a کوچکتر باشد استفاده از هیپ فیبوناتچی به مراتب بهتر از استفاده از هیپ دوجمله‌ای است. استفاده از هیپ‌های فیبوناتچی برای صف‌های اولویت‌دار زمان اجرای بعضی از الگوریتم‌های مهم را بهبود می‌بخشد، مثل الگوریتم دیکسترا برای محاسبه کوتاهترین مسیر در گراف، یا الگوریتم پریم برای محاسبه درخت فراگیر مینیمم در یک گراف. هیپ فیبوناتچی مجموعه‌ای از درخت هاست خصوصیت مینیمم هیپ را داراست، به عبارتی، کلید فرزند همواره بزرگتر یا مساوی کلید پدر است؛ بنابراین کوچکترین کلید همواره در ریشهٔ یکی از درخت‌ها قرار دارد. در مقایسه با هیپ دو جمله‌ای، ساختار هیپ فیبوناتچی از قابلیت تغییرپذیری بیشتری برخوردار است. درخت‌ها شکل مشخصی ندارند و در بدترین حالت هیپ می‌تواند تمام عناصرش را در یک درخت جدا یا یک تک درخت با عمق n ذخیره کند. این قابلیت تغییرپذیری را می‌توان برای کند اجرا کردن برنامه‌ها به کار گرفت تا اجرای بعضی اعمال را به تأخیر انداخت. به‌طور مثال ادغام هیپ هارا می‌توان به آسانی با به هم پیوستن دو لیست از درخت‌ها انجام داد، و عمل کاهش کلید بعضی اوقات یک گره را از پدر جدا کرده و یک درخت جدید تشکیل می‌دهد. با این حال در برخی موارد بعضی از دستورها نیاز دارند که برای رسیدن به زمان مورد نظر در حال اجرا به پشته معرفی شوند. به‌طور خاص، درجه گره‌ها (در اینجا به معنی تعداد فرزندان) را کم در نظر گرفته‌ایم: هر گره دارای درجه حداکثر و اندازه زیر درخت گره از درجه k حداقل Fk + 2 است، که در آن Fk که k امین عدد فیبوناچی است. این امر از آنجا حاصل می‌شود که ما می‌توانیم حداکثر یک فرزند از هر گره غیرریشه را قطع کنیم. هنگامی که فرزند دوم قطع می‌شود، گره خود باید از پدر یا مادر خود بریده و تبدیل به ریشه درخت جدید شود (در زیر می‌توانید اثبات مرزهای درجه را ببینید). تعداد درختان در عملیات حذف کوچکترین مقدار کاهش می‌یابد، که در آن درختان با هم مرتبط هستند. | ## بخش 2: هرم فیبوناچی | با توجه به ساختار راحت آن، انجام بعضی اعمال زمان طولانی لازم دارد در حالی که بعضی دیگر به سرعت انجام می‌شوند. در تحلیل زمان اجرای سرشکن ما وانمود می‌کنیم که اعمال خیلی سریع، کندتر از زمانی که باید اجرا شوند اجرا می‌شوند. این زمان ذخیره شده را می‌توان در هر زمانی با استفاده از تابع پتانسیل محاسبه نمود. گره علامت دار به گره‌ای گفته می‌شود که حداقل یکی از فرزندانش قطع شده باشد از زمانی که این گره خود فرزند گره دیگری شده بود (تمام ریشه‌ها بدون علامتند). این واحد زمان را می‌توان برای پیوند دادن یک درخت با درخت دیگر در زمان سرشکن صفر استفاده کرد. اگر این اتفاق بیفتد، گره تبدیل به یک ریشه می‌شود و واحد زمان دوم در آن ذخیره می‌شود، مانند بقیه ریشه‌ها. اجرای دستورها برای انجام سریع عملیات الحاق و پاک کردن، ریشه‌های تمام درختان توسط یک لیست پیوندی دوسویه به هم پیوند داده شده‌اند. عمل یافتن کوچکترین مقدار الان دیگر بی‌اهمیت است چونکه ما اشاره گری به گره داریم که حاوی آن است. این عمل پتانسیل هیپ را تحت تأثیر قرار نمی‌دهد، بنابراین مقدار دو هزینه سرشکن و واقعی ثابت خواهند ماند. همان‌طور که در بالا اشاره شد، عمل ادغام صرفاً با الحاق لیست ریشه‌های درخت دو هیپ انجام می‌شود. این عمل می‌تواند در زمان ثابت انجام شود و پتانسیل تغییر نکند، که باز هم منجر به زمان سرشکن ثابت می‌شود. این عمل نیز در زمان ثابت انجام می‌شود، و پتانسیل یک واحد افزایش می‌یابد، به خاطر اینکه تعداد درختان افزایش می‌یابد؛ بنابراین این عمل سرشکن نیز ثابت است. اگر تعداد فرزندان d باشد، زمان O(d) برای پردازش ریشه‌های جدید لازم خواهد بود و پتانسیل به اندازه d-۱ افزایش می‌یابد؛ بنابراین زمان اجرای سرشکن این فاز خواهد بود O(d)=O(log n). برای کامل کردن عمل استخراج مینیمم، باید اشاره گر به ریشه حاوی مینیمم را به روز کنیم. زمانی که دو ریشه u و v درجه یکسانی داشته باشند، ما یکی از آن‌ها را فرزند دیگری قرار می‌دهیم در نتیجه آن که کلید کوچکتری دارد ریشه باقی می‌ماند. برای یافتن درختان هم درجه، آرایه‌ای با طول O(log n) و که به ریشه از هر درجه یک اشاره گر نگه می‌داریم. | ## بخش 3: هرم فیبوناچی | وقتی ریشه دومی از یک درجه پیدا شود، آن دو به پیوند داده می‌شوند و آرایه به روز می‌شود. در فاز سوم ریشه‌های باقی‌مانده را بررسی می‌کنیم و مینیمم را پیدا می‌کنیم، این عمل زمان O(log n) می‌گیرد و پتانسیل تغییر نمی‌کند. این گره همانند دو جد علامت زده اش از درخت ریشه در ۱ جدا می‌شود و به عنوان ریشه جدید قرار می‌گیرد. عمل کاهش کلید گره را می‌گیرد، کلید را کاهش می‌دهد و اگر خاصیت هیپ در حال از بین رفتن بود (کلید جدید کوچکتر از کلید والدین باشد)، گره از والدینش جدا می‌شود. تمام این درختان به جز اولی، علامت دار هستند اما به عنوان ریشه بدون علامت می‌شوند. زمان واقعی برای اجرای عمل قطع کردن O(k) بود، بنابراین هزینه اجرای سرشکن ثابت است. نهایتاً، عمل پاک کردن را می‌توان به آسانی با کاهش کلید عنصر تا بینهایت منفی، و آن را به مینیمم هیپ تبدیل می‌کند. اثبات مرزهای درجه اجرای سرشکن یک هیپ فیبوناتچی بستگی به درجه (تعداد فرزندان) ریشه درخت O(log n) دارد، که در آن n اندازه هیپ است. در اینجا ما می‌خواهیم نشان دهیم که اندازه (زیر) درخت که ریشه در گره x با درجه d در هیپ دارد، باید اندازه حداقل Fd+2، که Fk در آن k امین عدد فیبوناتچی است. مرز درجه از این و اینکه برای همه اعداد صحیح ، که در آن ، نتیجه می‌شود (بعدها خواهیم داشت ، که از آن نتیجه می‌شود ). گره دلخواه x را در هیپ در نظر بگیرید (نیازی نیست که ریشه یکی از درختان اصلی باشد). استقراء:فرض کنید x ارتفاع و درجه مثبت داشته باشد، فرض می‌کنیم y۱، y۲، …، yd فرزندان x باشند که به ترتیب زمان مرتب شده‌اند (y۱ اولین عنصر باشد)، و c۱، c۲، …، cd به ترتیب درجه هایشان باشند. چون درخت‌های فقط زمانی با هم ادغام می‌شوند که درجه ریشه هایشان برابر باشد، نتیجه می‌شود که yi زمانی که فرزند x می‌شد حداقل از درجه i-۱ بوده. از آن زمان تا گنون، yi می‌تواند حداکثر یک فرزند را از دست داده باشد (با توجه به رویه علامت گذاری)، بنابراین ci حداقل i-۲ است، این ادعای ما را اثبات می‌کند. گره‌های x و y۱ هر کدام حداقل یک واحد به اندازه x اضافه می‌کنند، بنابراین خواهیم داشت: با استفاده از یک استقراء ساده به این نتیجه می‌رسیم که برای هر ، . بدترین حالت هر چند زمان اجرای کل این اعمال که از یک ساختار خالی شروع می‌شوند با مرزهای مشخص شده محدود شده است، اما تعداد کمی از اعمال مثل پاک کردن، و پاک کردن مینیمم از آن جهت که زمان اجرایشان خطی است، زمان طولانی برای اجرا خواهند داشت. | ## جمع‌بندی | به همین دلیل هیپ فیبوناتچی و دیگر داده ساختارهای سرشکن برای محاسبات زمان واقعی مناسب نیستند.