ערימה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תיקון סדר פעולות חשבון |
clean up, replaced: – ← – באמצעות AWB |
||
שורה 28:
===ערימת פיבונאצ'י===
{{ערך מורחב|ערימת פיבונאצ'י}}
ערימות פיבונאצ'י ממומשות גם הן בתור אוסף של עצים, בדומה לערימות בינומיות, אך העצים אינם חייבים להיות עצים בינומיים. בשל כך ערימת פיבונאצ'י היא גמישה יותר, ומהירה יותר כאשר מתייחסים ל[[סיבוכיות]] משוערכת של זמן הריצה של הפעולות שבה (כלומר, לא בודקים את הזמן שלוקחת פעולה בודדת, אלא את הזמן שלוקחת סדרה של פעולות).
ערימת פיבונאצ'י משמשת לשיפור זמן הריצה של אלגוריתמים דוגמת [[אלגוריתם דייקסטרה]] ו[[האלגוריתם של פרים]].
שורה 35:
מקובל לייצג ערימה על ידי מערך סטטי (משתי סיבות עיקריות: טבעי וקל למימוש, יעיל בזיכרון וזמן ריצה).{{ש}}כאמור בערימה (מקסימום) הנתון בכל קודקוד גדול שווה משני ילדיו. ערימה היא עץ שלם, פרט אולי לרמה האחרונה שבה העלים מתחילים משמאל לימין.
גודלו הלוגי של מערך יהיה n כמספר הקודקודים וישמר במשתנה נפרד heapSize.
# מערך בו השורש במקום 0.
שורה 50:
==ראו גם==
*[[מיון ערימה]]
==קישורים חיצוניים==
<div class="mw-content-ltr">
*{{cite journal|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan |title=Fibonacci heaps and their uses in improved network optimization algorithms| url = http://www.cl.cam.ac.uk/~sos22/supervise/dsaa/fib_heaps.pdf | format = PDF |journal=Journal of the Association for Computing Machinery|volume=34|year=1987|pages=
</div>
{{מבני נתונים}}
[[קטגוריה:מבני נתונים]]
[[קטגוריה:עצים (גרפים)]]
| |||