هرم فیبوناچی

در علوم کامپیوتر، هیپ فیبوناتچی به داده ساختار هیپی گفته می‌شود که شامل انبوهی از درخت‌ها است. این هیپ زمان اجرای سرشکن بهتری نسبت به هیپ دوجمله‌ای دارد. هیپ‌های فیبوناتچی توسط مایکل فردمن و رابرت تارجن در سال ۱۹۸۴ ایجاد شده‌اند، و برای اولین بار در یک مقاله علمی در سال ۱۹۸۷ منتشر شدند. ایده نام هیپ فیبوناتچی از اعداد فیبوناتچی که در اجرای تحلیل زمانی از آن استفاده می‌شود، گرفته شده‌است.

اعمال درج، یافتن کوچکترین مقدار، کاهش کلید، و ادغام (الحاق) در زمان سرشکن ثابت کار می‌کنند. اعمال حذف و حذف کوچکترین مقدار در زمان سرشکن $O(logn)$ کار می‌کنند. این بدین معناست که با شروع از یک داده ساختار خالی، a عمل از دستورها گروه اول و b عمل از دستورها گروه دوم، زمان اجرای $O(a+blogn)$ خواهد داشت. در هیپ‌های دو جمله انجام چنین عملی نیاز به زمان اجرای $O((a+b)log(n))$ دارد؛ بنابراین زمانی که b از a کوچکتر باشد استفاده از هیپ فیبوناتچی به مراتب بهتر از استفاده از هیپ دوجمله‌ای است.

استفاده از هیپ‌های فیبوناتچی برای صف‌های اولویت‌دار زمان اجرای بعضی از الگوریتم‌های مهم را بهبود می‌بخشد، مثل الگوریتم دیکسترا برای محاسبه کوتاهترین مسیر در گراف، یا الگوریتم پریم برای محاسبه درخت فراگیر مینیمم در یک گراف.

ساختار

شکل ۱: نمونه یک هیپ فیبوناتچی، با سه درخت از درجه ۰٬۱، و ۳. سه راس علامت دارند (رنگ آبی)، بنابراین پتانسیل هیپ ۹ است.

هیپ فیبوناتچی مجموعه‌ای از درخت هاست خصوصیت مینیمم هیپ را داراست، به عبارتی، کلید فرزند همواره بزرگتر یا مساوی کلید پدر است؛ بنابراین کوچکترین کلید همواره در ریشهٔ یکی از درخت‌ها قرار دارد. در مقایسه با هیپ دو جمله‌ای، ساختار هیپ فیبوناتچی از قابلیت تغییرپذیری بیشتری برخوردار است. درخت‌ها شکل مشخصی ندارند و در بدترین حالت هیپ می‌تواند تمام عناصرش را در یک درخت جدا یا یک تک درخت با عمق n ذخیره کند. این قابلیت تغییرپذیری را می‌توان برای کند اجرا کردن برنامه‌ها به کار گرفت تا اجرای بعضی اعمال را به تأخیر انداخت. به‌طور مثال ادغام هیپ هارا می‌توان به آسانی با به هم پیوستن دو لیست از درخت‌ها انجام داد، و عمل کاهش کلید بعضی اوقات یک گره را از پدر جدا کرده و یک درخت جدید تشکیل می‌دهد.

با این حال در برخی موارد بعضی از دستورها نیاز دارند که برای رسیدن به زمان مورد نظر در حال اجرا به پشته معرفی شوند. به‌طور خاص، درجه گره‌ها (در اینجا به معنی تعداد فرزندان) را کم در نظر گرفته‌ایم: هر گره دارای درجه حداکثر $O(logn)$ و اندازه زیر درخت گره از درجه k حداقل F_k + 2 است، که در آن F_k که k امین عدد فیبوناچی است. این امر از آنجا حاصل می‌شود که ما می‌توانیم حداکثر یک فرزند از هر گره غیرریشه را قطع کنیم. هنگامی که فرزند دوم قطع می‌شود، گره خود باید از پدر یا مادر خود بریده و تبدیل به ریشه درخت جدید شود (در زیر می‌توانید اثبات مرزهای درجه را ببینید). تعداد درختان در عملیات حذف کوچکترین مقدار کاهش می‌یابد، که در آن درختان با هم مرتبط هستند.

با توجه به ساختار راحت آن، انجام بعضی اعمال زمان طولانی لازم دارد در حالی که بعضی دیگر به سرعت انجام می‌شوند. در تحلیل زمان اجرای سرشکن ما وانمود می‌کنیم که اعمال خیلی سریع، کندتر از زمانی که باید اجرا شوند اجرا می‌شوند. این زمان اضافه در انتها از زمان اعمال کند کم می‌شود. این زمان ذخیره شده را می‌توان در هر زمانی با استفاده از تابع پتانسیل محاسبه نمود. پتانسیل هیپ فیبوناتچی با استفاده از فرمول زیر محاسبه می‌شود:

Potential = t + 2m

که t در آن تعداد درختان هیپ فیبوناتچی است، و m تعداد گره‌های علامت گزاری شده‌است. گره علامت دار به گره‌ای گفته می‌شود که حداقل یکی از فرزندانش قطع شده باشد از زمانی که این گره خود فرزند گره دیگری شده بود (تمام ریشه‌ها بدون علامتند).

بنابراین، ریشه هر درخت در هیپ یک واحد زمان در خود ذخیره دارد. این واحد زمان را می‌توان برای پیوند دادن یک درخت با درخت دیگر در زمان سرشکن صفر استفاده کرد. هم چنین، هر گره علامت گذاری شده دو واحد زمان در خود ذخیره دارد. یک واحد برای جدا کردن گره از والدینش به کار می‌رود. اگر این اتفاق بیفتد، گره تبدیل به یک ریشه می‌شود و واحد زمان دوم در آن ذخیره می‌شود، مانند بقیه ریشه‌ها.

اجرای دستورها

برای انجام سریع عملیات الحاق و پاک کردن، ریشه‌های تمام درختان توسط یک لیست پیوندی دوسویه به هم پیوند داده شده‌اند. فرزندان هر گره هم به همین روش به هم پیوند داده شده‌اند. برای هر گره، فرزندان آن را چه گره علامت دار باشد چه نباشد، حفظ می‌کنیم. هم چنین اشاره گری به ریشه که حاوی کوچکترین کلید است در نظر می‌گیریم.

عمل یافتن کوچکترین مقدار الان دیگر بی‌اهمیت است چونکه ما اشاره گری به گره داریم که حاوی آن است. این عمل پتانسیل هیپ را تحت تأثیر قرار نمی‌دهد، بنابراین مقدار دو هزینه سرشکن و واقعی ثابت خواهند ماند. همان‌طور که در بالا اشاره شد، عمل ادغام صرفاً با الحاق لیست ریشه‌های درخت دو هیپ انجام می‌شود. این عمل می‌تواند در زمان ثابت انجام شود و پتانسیل تغییر نکند، که باز هم منجر به زمان سرشکن ثابت می‌شود. عمل درج را می‌توان با ساختن یک هیپ جدید با یک عضو و انجام عمل ادغام، انجام داد. این عمل نیز در زمان ثابت انجام می‌شود، و پتانسیل یک واحد افزایش می‌یابد، به خاطر اینکه تعداد درختان افزایش می‌یابد؛ بنابراین این عمل سرشکن نیز ثابت است.

هیپ فیبوناتچی شکل ۱ پس از اولین فاز استخراج مینیمم، گره با کلید ۱ (مینیمم) پاک شده و فرزندانش به عنوان درختان جدید اضافه شده‌اند.

عمل استخراج مینیمم (مانند پاک کردن مینیمم) در سه فاز انجام می‌شود. اول ریشه‌ای که حاوی مینیمم است یافته و آن را پاک می‌کنیم. فرزندانش ریشه‌های درختان جدید خواهند شد. اگر تعداد فرزندان d باشد، زمان O(d) برای پردازش ریشه‌های جدید لازم خواهد بود و پتانسیل به اندازه d-۱ افزایش می‌یابد؛ بنابراین زمان اجرای سرشکن این فاز خواهد بود O(d)=O(log n).

هیپ فیبوناتچی شکل ۱ پس از اینکه استخراج مینیمم کامل شده است، ابتدا گره‌های ۳ و ۶ به هم پیوند زده می‌شوند. سپس نتیجه به درختی که ریشه در گره ۲ دارد پیوند داده می‌شود. در آخر مینیمم جدید پیدا می‌شود .

برای کامل کردن عمل استخراج مینیمم، باید اشاره گر به ریشه حاوی مینیمم را به روز کنیم. متأسفانه ممکن است n ریشه برای بررسی کردن وجود داشته باشد. در فاز دوم با پیوند دادن ریشه‌های هم درجه تعداد ریشه‌ها را کاهش می‌دهیم. زمانی که دو ریشه u و v درجه یکسانی داشته باشند، ما یکی از آن‌ها را فرزند دیگری قرار می‌دهیم در نتیجه آن که کلید کوچکتری دارد ریشه باقی می‌ماند. درجه اش یک واحد افزایش می‌یابد. این عمل تا آنجا ادامه می‌یابد تا همه ریشه‌ها درجه متفاوتی داشته باشند. برای یافتن درختان هم درجه، آرایه‌ای با طول O(log n) و که به ریشه از هر درجه یک اشاره گر نگه می‌داریم. وقتی ریشه دومی از یک درجه پیدا شود، آن دو به پیوند داده می‌شوند و آرایه به روز می‌شود. زمان اجرای واقعی آن O(log n +m) که m تعداد ریشه‌ها در اول فاز دوم است. در آخر حداکثر O(log n) ریشه دارد (چون هر کدام درجه متفاوتی دارد). بنابراین کاهش پتانسیل حداقل m-O(log n) زمان اجرای سرشکن O(log n).

در فاز سوم ریشه‌های باقی‌مانده را بررسی می‌کنیم و مینیمم را پیدا می‌کنیم، این عمل زمان O(log n) می‌گیرد و پتانسیل تغییر نمی‌کند. پس زمان اجرای سرشکن کل استخراج مینیمم خواهد بود O(log n).

هیپ فیبوناتچی شکل ۱ پس از کاهش کلید گره از ۹ به ۰. این گره همانند دو جد علامت زده اش از درخت ریشه در ۱ جدا می‌شود و به عنوان ریشه جدید قرار می‌گیرد.

عمل کاهش کلید گره را می‌گیرد، کلید را کاهش می‌دهد و اگر خاصیت هیپ در حال از بین رفتن بود (کلید جدید کوچکتر از کلید والدین باشد)، گره از والدینش جدا می‌شود. اگر پدر ریشه نباشد، علامت زده می‌شود. اگر از قبل علامت زده باشد، قطع می‌شود و پدرش علامت زده می‌شود. آنقدر بالا می‌رویم تا یا به یک ریشه برسیم یا به یک گره علامت نزده. در طول این اعمال تعدادی درخت جدید به‌طور مثال k تا به وجود می‌آوریم. تمام این درختان به جز اولی، علامت دار هستند اما به عنوان ریشه بدون علامت می‌شوند. یک گره می‌تواند علامت دار شود؛ بنابراین کاهش پتانسیل آن k-۲ خواهد بود. زمان واقعی برای اجرای عمل قطع کردن O(k) بود، بنابراین هزینه اجرای سرشکن ثابت است.

نهایتاً، عمل پاک کردن را می‌توان به آسانی با کاهش کلید عنصر تا بینهایت منفی، و آن را به مینیمم هیپ تبدیل می‌کند. سپس عمل استخراج مینیمم را صدا می‌زنیم تا آن را پاک کنیم. هزینه اجرای سرشکن این عمل O(log n).

اثبات مرزهای درجه

اجرای سرشکن یک هیپ فیبوناتچی بستگی به درجه (تعداد فرزندان) ریشه درخت O(log n) دارد، که در آن n اندازه هیپ است. در اینجا ما می‌خواهیم نشان دهیم که اندازه (زیر) درخت که ریشه در گره x با درجه d در هیپ دارد، باید اندازه حداقل F_d+2، که F_k در آن k امین عدد فیبوناتچی است. مرز درجه از این و اینکه $F_{d+2}\geq \varphi ^{d}$ برای همه اعداد صحیح $d\geq 0$، که در آن $\varphi =(1+{\sqrt {5}})/2\doteq 1.62$، نتیجه می‌شود (بعدها خواهیم داشت $n\geq F_{d+2}\geq \varphi ^{d}$، که از آن نتیجه می‌شود $\varphi$).

گره دلخواه x را در هیپ در نظر بگیرید (نیازی نیست که ریشه یکی از درختان اصلی باشد). Size(x) را اندازه درختی که ریشه در گره x دارد تعریف می‌کنیم (تعداد فرزندان x به علاوه خود x). با استقراء روی ارتفاع x (طول ساده‌ترین مسیر از x به شاخه فرزند)، اثبات می‌کنیم که size(x) ≥ F_d+2، که در آن d درجه x است.

شرایط اولیه: اگر ارتفاع x صفر باشد، آنگاه d صفر، و Size(x) = ۱ خواهد بود.

استقراء:فرض کنید x ارتفاع و درجه مثبت داشته باشد، فرض می‌کنیم y_۱، y_۲، …، y_d فرزندان x باشند که به ترتیب زمان مرتب شده‌اند (y_۱ اولین عنصر باشد)، و c_۱، c_۲، …، c_d به ترتیب درجه هایشان باشند. ما ادعا می‌کنیم که برای هر i با شرط ۲≤i≤d، خواهیم داشت c_i ≥ i-۲. قبل از اینکه y_i فرزند x شود، y_۱،... ،y_i-1 فرزندهای x بوده‌اند، بنابراین x از درجه i-۱ بوده است. چون درخت‌های فقط زمانی با هم ادغام می‌شوند که درجه ریشه هایشان برابر باشد، نتیجه می‌شود که y_i زمانی که فرزند x می‌شد حداقل از درجه i-۱ بوده. از آن زمان تا گنون، y_i می‌تواند حداکثر یک فرزند را از دست داده باشد (با توجه به رویه علامت گذاری)، بنابراین c_i حداقل i-۲ است، این ادعای ما را اثبات می‌کند.

از آن جهت که ارتفاع تمام y_iها کمتر از x است، می‌توانیم فرض استقراء را به آن‌ها اعمال کنیم تا size(y_i) ≥ F_ci+۲ ≥ F_(i-۲)+۲ = F_i را بدست آوریم. گره‌های x و y_۱ هر کدام حداقل یک واحد به اندازه x اضافه می‌کنند، بنابراین خواهیم داشت:

${\textbf {size}}(x)\geq 2+\sum _{i=2}^{d}{\textbf {size}}(y_{i})\geq 2+\sum _{i=2}^{d}F_{i}=1+\sum _{i=0}^{d}F_{i}.$

با استفاده از یک استقراء ساده به این نتیجه می‌رسیم که برای هر $d\geq 0$، $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$. که مرز پایین Size(x) را به ما می‌دهد.

بدترین حالت

هر چند زمان اجرای کل این اعمال که از یک ساختار خالی شروع می‌شوند با مرزهای مشخص شده محدود شده است، اما تعداد کمی از اعمال مثل پاک کردن، و پاک کردن مینیمم از آن جهت که زمان اجرایشان خطی است، زمان طولانی برای اجرا خواهند داشت. به همین دلیل هیپ فیبوناتچی و دیگر داده ساختارهای سرشکن برای محاسبات زمان واقعی مناسب نیستند.

خلاصه زمان‌های اجرا

	لیست پیوندی	درخت دودویی متعادل	هیپ مینیمم	هیپ فیبوناتچی	صف برودال
درج	O(1)	O(log n)	O(log n)	O(1)	O(1)
دسترسی به مینیمم	O(n)	O(log n) or O(1) (**)	O(1)	O(1)	O(1)
پاک کردن مینیمم	O(n)	O(log n)	O(log n)	O(log n)*	O(log n)
کاهش کلید	O(1)	O(log n)	O(log n)	O(1)*	O(1)
پاک کردن	O(n)	O(log n)	O(log n)	O(log n)*	O(log n)
ادغام	O(1)	O(m log(n+m))	O(m log(n+m))	O(1)	O(1)

(*)زمان سرشکن
(**)با تغییرات جزئی در درخت دودویی معمولی

منابع

• Fredman M. L. & Tarjan R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM ۳۴(۳)، ۵۹۶–۶۱۵.
• توماس اچ کورمن، Charles E. Leiserson، رونالد ریوست، and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها، Second Edition. انتشارات ام‌آی‌تی and McGraw-Hill، ۲۰۰۱. شابک ‎۰−۲۶۲−۰۳۲۹۳−۷. Chapter 20: Fibonacci Heaps، pp.۴۷۶–۴۹۷.
• Brodal، G. S. ۱۹۹۶. Worst-case efficient priority queues. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta، Georgia، United States، January ۲۸–۳۰، ۱۹۹۶). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics، Philadelphia، PA، ۵۲–۵۸.

پیوند به بیرون

• شبیه‌سازی هیپ فیبوناچی با اپلت جاوا
• کد C هیپ فیبوناتچی
• سودو کد الگوریتم هیپ فیبوناتچی