שלום.
מישהו יכול להסביר לי את הקוד של האלגוריתם של Heapify?
איך זה עוזר לי לסדר את הערימה?
פסאודו קוד של האלגוריתם:
Heapify(A,i)
l <- LEFT(i)
r <- RIGHT(i)
if l <= heapsize[A] and A[l] > A[i]
then largest <- l
else largest <- i
if r<=heapsize[A] and A[r] > A[largest]
then largest <- r
if largest != i
then exchange A[i] <-> A[largest]
Heapify(A,largest)
פעולת Heapify (נקראת גם BubbleDown או Sift Down) נועדה כדי לתקן את הערימה. האלגוריתם מסדר מחדש את הערימה כדי לשמור על תכונתה (ערימת מינימום או מקסימום), כלומר מפתח של צומת השורש הוא “הכי קיצוני” (קטן או גדול) ביחס לכל שאר המפתחות של הילדים. אם המפתח של צומת השורש הוא לא “הכי קיצוני” אז אנו מבצעים החלפה עם הצומת בעל המפתח “הכי קיצוני” מבין בניו ואז באופן רקורסיבי מבצעים את הפעולה בתת-העץ.
כדי להמחיש את הרעיון בצורה הטובה ביותר, נגדיר ערימת מקסימום ונניח והגענו למצב המופיע בתרשים (a):
מאחר ומדובר בערימת מקסימום נשים לב כי לבן השמאלי של השורש, בעל המפתח 4 ישנה בעיה - הוא יותר קטן משני בניו. לפי האלגוריתם נבצעה החלפה בינו לבין הבן “הכי קיצוני” ביחס לתכונת הערימה, כלומר נחליף בינו לבין הבן השמאלי בעל המפתח 14 (שכן הוא בעל המפתח המקסימלי מבין שני בניו). לכן קיבלנו את תרשים (b). כעת שוב נבצע את פעולה Heapify על המפתח 4 ונבדוק אם הצומת בעל מפתח 4 עדיין מקיים את תכונת הערימה. נשים לב כי הוא עדיין לא מקיים את תכונת הערימה שכן אחד מבניו בעל מפתח גדול יותר מ-4 ולכן שוב נבצע החלפה בין צומת בעל מפתח 8 לבין צומת בעל מפתח 4 כך שנקבל את שרטוט (c). קיבלנו ערימת מקסימום מסודרת.
לגבי הסיבוכיות, אם הצומת הראשוני הוא עלה אז סיבוכיות הפעולה הינה O(1) ואם הוא שורש אז סיבוכיות הפעולה הינה O(\log n). לכן סה"כ סיבוכיות הפעולה במקרה הגרוע הינה O(\log n).
מקווה שמובן, בהצלחה 