מבני נתונים ומבוא לאלגוריתמים

ברוכים הבאים ליחידת הלימוד על ערימות ותורי קדימויות בקורס "מבני נתונים ומבוא לאלגוריתמים" (20407). יחידה זו חיונית להבנת מבני נתונים מתקדמים ואלגוריתמי מיון יעילים. נתמקד בהגדרת הערימה, תכונותיה, פעולותיה הבסיסיות, ניתוח סיבוכיותן, ויישומיה המרכזיים בתורי קדימויות ובמיון. שימו לב לדגשים על ניתוח סיבוכיות, הבנת פעולות הליבה, ויישום מעשי, שהם קריטיים להצלחה בבחינה.

מבוא לערימות ותכונותיהן

מהי ערימה?

ערימה (Heap) היא מבנה נתונים מבוסס עץ בינארי כמעט שלם (Complete Binary Tree) המקיים תכונה נוספת הנקראת "תכונת הערימה". ייצוגה הנפוץ והיעיל ביותר הוא באמצעות מערך.

עץ בינארי כמעט שלם: עץ בינארי שבו כל הרמות מלאות, למעט אולי הרמה האחרונה, והצמתים ברמה האחרונה מלאים משמאל לימין.

תכונות מפתח של ערימה

ערימת מקסימום (Max-Heap)

בכל צומת i, ערך המפתח של הצומת גדול או שווה לערכי המפתחות של ילדיו. כלומר, השורש מכיל את האיבר הגדול ביותר.

ערימת מינימום (Min-Heap)

בכל צומת i, ערך המפתח של הצומת קטן או שווה לערכי המפתחות של ילדיו. כלומר, השורש מכיל את האיבר הקטן ביותר.

ייצוג ערימה במערך: ערימה בינארית כמעט שלמה ניתנת לייצוג יעיל במערך חד-ממדי. עבור צומת במיקום i (בהנחה שהאינדקסים מתחילים מ-1):

הורה (Parent) נמצא במיקום floor(i/2).
ילד שמאלי (Left Child) נמצא במיקום 2i.
ילד ימני (Right Child) נמצא במיקום 2i + 1.

פעולות בסיסיות על ערימות וניתוח סיבוכיותן

HEAPIFY (הורדת איבר)

פעולת HEAPIFY (לרוב MAX-HEAPIFY או MIN-HEAPIFY) שומרת על תכונת הערימה. היא מופעלת על צומת i, בהנחה שהעצים המקוריים של ילדיו (אם קיימים) כבר ערימות. היא משווה את הצומת i עם ילדיו, ומחליפה אותו עם הילד הגדול/קטן ביותר (בהתאם לסוג הערימה) אם תכונת הערימה מופרת. הפעולה ממשיכה באופן רקורסיבי על תת-העץ שהושפע מההחלפה.

סיבוכיות זמן: O(log n), כאשר n הוא מספר האיברים בערימה. הסיבה היא שהפעולה יורדת בעץ לכל היותר כגובה העץ, שהוא log n.

BUILD-HEAP (בניית ערימה)

פעולת BUILD-HEAP בונה ערימה מתוך מערך נתון באופן לא ממוין. היא עושה זאת על ידי הפעלת HEAPIFY על כל הצמתים שאינם עלים, החל מהצומת האחרון שאינו עלה (floor(n/2)) ועד לשורש (אינדקס 1).

סיבוכיות זמן: O(n).

מדוע BUILD-HEAP הוא O(n) ולא O(n log n)?: זוהי נקודה קריטית לבחינה! למרות שכל קריאה ל-HEAPIFY אורכת O(log n), וקיימים O(n) צמתים שאינם עלים, סכום זמני הריצה אינו O(n log n). הסיבה היא שרוב הקריאות ל-HEAPIFY מבוצעות על צמתים קרובים לעלים, שגובה תת-העץ שלהם קטן. ניתוח מדויק יותר באמצעות סכימת טורים גיאומטריים מוכיח שסיבוכיות הזמן הכוללת היא O(n). הבנה זו חיונית!

INSERT (הכנסה) ו-EXTRACT-MAX/MIN (הוצאה)

INSERT: מוסיף איבר חדש לערימה. האיבר מתווסף לסוף המערך (המיקום הפנוי הבא), ולאחר מכן "עולה" בעץ (באמצעות פעולה דומה ל-HEAPIFY אך כלפי מעלה) עד שתכונת הערימה נשמרת. סיבוכיות: O(log n).
EXTRACT-MAX/MIN: מוציא את האיבר בעל הקדימות הגבוהה ביותר (השורש). השורש מוחלף באיבר האחרון במערך, האיבר האחרון מוסר, ולאחר מכן מופעלת HEAPIFY על השורש החדש כדי לשמור על תכונת הערימה. סיבוכיות: O(log n).

יישומים עיקריים: תורי קדימויות ומיון ערימה

תורי קדימויות (Priority Queues)

תור קדימויות הוא מבנה נתונים מופשט התומך בפעולות הכנסה והוצאת האיבר בעל הקדימות הגבוהה ביותר. ערימה היא המימוש הנפוץ והיעיל ביותר לתור קדימויות.

תור קדימויות: מבנה נתונים התומך בפעולות: INSERT(x) (הכנסת איבר), EXTRACT-MAX() או EXTRACT-MIN() (הוצאת האיבר בעל הקדימות הגבוהה ביותר), ו-PEEK() או MAXIMUM() (הצגת האיבר בעל הקדימות הגבוהה ביותר ללא הוצאה).

מיון ערימה (Heapsort)

מיון ערימה הוא אלגוריתם מיון יעיל המשתמש בערימת מקסימום. הוא מבצע מיון במקום (in-place) וסיבוכיות הזמן שלו היא O(n log n) במקרה הגרוע ביותר.

שלבים:
1. בונים ערימת מקסימום מהמערך הנתון באמצעות BUILD-MAX-HEAP (בזמן O(n)).
2. מוציאים את האיבר הגדול ביותר (השורש) ומחליפים אותו באיבר האחרון בערימה. מקטינים את גודל הערימה באחד.
3. מפעילים MAX-HEAPIFY על השורש החדש (בזמן O(log n)).
4. חוזרים על שלבים 2 ו-3 n-1 פעמים. האיברים הממוינים נאספים בסוף המערך.
סיבוכיות זמן: O(n log n) (בגלל n-1 קריאות ל-HEAPIFY שכל אחת אורכת O(log n)).
סיבוכיות מקום: O(1) (מיון במקום).

דגשים לבחינה והשוואות

השוואת יעילות של תורי קדימויות

הבנת היתרונות והחסרונות של מימושים שונים לתורי קדימויות היא קריטית.

ערימה (Heap)

INSERT: O(log n)
EXTRACT-MAX/MIN: O(log n)
MAXIMUM/MINIMUM: O(1)

מערך ממוין

INSERT: O(n)
EXTRACT-MAX/MIN: O(1)
MAXIMUM/MINIMUM: O(1)

מערך לא ממוין

INSERT: O(1)
EXTRACT-MAX/MIN: O(n)
MAXIMUM/MINIMUM: O(n)

נקודות חשובות נוספות לבחינה

הבנת תכונות הערימה: היכולת לזהות האם מבנה נתון נתון הוא ערימה חוקית.
מעקב ידני: היכולת לבצע מעקב צעד אחר צעד של פעולות HEAPIFY, BUILD-HEAP, INSERT, EXTRACT-MAX על ערימה נתונה.
שינוי מפתחות: פעולות INCREASE-KEY ו-DECREASE-KEY וסיבוכיותן (O(log n)).
יישומים: זיהוי מתי ערימה היא מבנה הנתונים המתאים ביותר לבעיה נתונה (לדוגמה, אלגוריתם דייקסטרה, מינימום עץ פורש).

שאלות לדיון

הסבירו במילים שלכם מדוע ייצוג ערימה במערך הוא יעיל, וכיצד הוא מאפשר גישה מהירה להורים וילדים.
תארו את ההבדלים המהותיים בין ערימת מקסימום לערימת מינימום, והביאו דוגמה לשימוש בכל אחת מהן.
בהינתן מערך מספרים, הדגימו צעד אחר צעד כיצד תבנו ממנו ערימת מקסימום באמצעות אלגוריתם BUILD-MAX-HEAP. נתחו את הסיבוכיות של תהליך זה.
השוו את מיון ערימה (Heapsort) למיון מיזוג (Mergesort) ולמיון מהיר (Quicksort) מבחינת סיבוכיות זמן, סיבוכיות מקום ויציבות.

נקודות לתשובת מודל

הגדרת ערימה ותכונותיה: עץ בינארי כמעט שלם, תכונת הערימה (מקסימום/מינימום), ייצוג במערך ונוסחאות לגישה להורים
מצאתם טעות או שחסר משהו?