هرم فیبوناچی
From Wikipedia, the free encyclopedia
در علوم کامپیوتر، هیپ فیبوناتچی به داده ساختار هیپی گفته میشود که شامل انبوهی از درختها است. این هیپ زمان اجرای سرشکن بهتری نسبت به هیپ دوجملهای دارد. هیپهای فیبوناتچی توسط مایکل فردمن و رابرت تارجن در سال ۱۹۸۴ ایجاد شدهاند، و برای اولین بار در یک مقاله علمی در سال ۱۹۸۷ منتشر شدند. ایده نام هیپ فیبوناتچی از اعداد فیبوناتچی که در اجرای تحلیل زمانی از آن استفاده میشود، گرفته شدهاست.
اعمال درج، یافتن کوچکترین مقدار، کاهش کلید، و ادغام (الحاق) در زمان سرشکن ثابت کار میکنند. اعمال حذف و حذف کوچکترین مقدار در زمان سرشکن کار میکنند. این بدین معناست که با شروع از یک داده ساختار خالی، a عمل از دستورها گروه اول و b عمل از دستورها گروه دوم، زمان اجرای خواهد داشت. در هیپهای دو جمله انجام چنین عملی نیاز به زمان اجرای دارد؛ بنابراین زمانی که b از a کوچکتر باشد استفاده از هیپ فیبوناتچی به مراتب بهتر از استفاده از هیپ دوجملهای است.
استفاده از هیپهای فیبوناتچی برای صفهای اولویتدار زمان اجرای بعضی از الگوریتمهای مهم را بهبود میبخشد، مثل الگوریتم دیکسترا برای محاسبه کوتاهترین مسیر در گراف، یا الگوریتم پریم برای محاسبه درخت فراگیر مینیمم در یک گراف.