יחידה 6: ערימות ותורי קדימויות

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

ערימות (Heaps) – המבנה והתכונות

ערימה היא מבנה נתונים מבוסס עץ בינארי, המקיים שתי תכונות מרכזיות המעניקות לו יעילות רבה ביישומים מסוימים.

תכונות הערימה:

• תכונת המבנה (Structure Property): הערימה היא עץ בינארי מלא. כלומר, כל הרמות מלאות למעט אולי הרמה האחרונה, והצמתים ברמה האחרונה מלאים משמאל לימין. תכונה זו מאפשרת לייצג ערימה ביעילות באמצעות מערך, ללא צורך במצביעים.
• תכונת הסדר (Heap Property):
  • ערימת מקסימום (Max-Heap): בכל צומת, הערך שלו גדול או שווה לערכי ילדיו. המשמעות היא שהאיבר הגדול ביותר נמצא תמיד בשורש הערימה.
  • ערימת מינימום (Min-Heap): בכל צומת, הערך שלו קטן או שווה לערכי ילדיו. המשמעות היא שהאיבר הקטן ביותר נמצא תמיד בשורש הערימה.

תור קדימויות (Priority Queue) – היישום המרכזי

תור קדימויות הוא מבנה נתונים מופשט (Abstract Data Type) המאפשר אחסון איברים ולשלוף תמיד את האיבר בעל הקדימות הגבוהה ביותר. ערימה היא המימוש הנפוץ והיעיל ביותר לתור קדימויות.

פעולות עיקריות בתור קדימויות מבוסס ערימה:

• הכנסה (Insert): מוסיף איבר חדש לתור. בערימה, האיבר מתווסף לסוף המערך (המיקום הפנוי הבא בעץ), ואז "מבעבע" כלפי מעלה (heapify-up) כדי לשמור על תכונת הערימה. סיבוכיות: O(log n).
• שליפת איבר בעל קדימות עליונה (Extract-Min/Max): מסיר ושולף את האיבר בעל הקדימות הגבוהה ביותר (השורש). בערימה, השורש מוחלף באיבר האחרון במערך, ואז האיבר החדש בשורש "מבעבע" כלפי מטה (heapify-down) כדי לשמור על תכונת הערימה. סיבוכיות: O(log n).
• הצצה (Peek/Find-Min/Max): מחזיר את האיבר בעל הקדימות הגבוהה ביותר מבלי להסירו. בערימה, זה פשוט החזרת ערך השורש. סיבוכיות: O(1).

מיון ערימה (Heapsort) – אלגוריתם מיון יעיל

מיון ערימה הוא אלגוריתם מיון מבוסס השוואות, המנצל את תכונות הערימה למיון מערך. הוא נחשב לאלגוריתם יעיל ושימושי.

שלבי אלגוריתם Heapsort:

1. בניית ערימה (Build Heap): הופכים את המערך הנתון לערימת מקסימום (או מינימום). פעולה זו מתבצעת על ידי הפעלת heapify-down על כל צומת שאינו עלה, החל מהצומת האחרון שאינו עלה ועד לשורש. סיבוכיות: O(n).
2. שליפה חוזרת ונשנית (Repeated Extraction): לאחר בניית הערימה, האיבר הגדול ביותר נמצא בשורש. מחליפים את השורש עם האיבר האחרון במערך, מקטינים את גודל הערימה באחד, ומפעילים heapify-down על השורש החדש כדי לשמור על תכונת הערימה. חוזרים על פעולה זו n-1 פעמים. סיבוכיות: O(n log n).

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

שאלות לדיון

• הסבר מדוע ייצוג ערימה באמצעות מערך הוא יעיל, וכיצד ניתן לחשב את אינדקסי הילדים וההורה של צומת נתון במערך.
• השווה בין מימוש תור קדימויות באמצעות ערימה לבין מימושים חלופיים כמו רשימה מקושרת ממוינת או מערך לא ממוין, בהתייחס לסיבוכיות זמן של פעולות הכנסה ושליפה.
• הדגם את פעולת מיון ערימה (Heapsort) על המערך [5, 13, 2, 25, 7, 17] והצג את מצב המערך לאחר כל שלב עיקרי.
• מהם היתרונות והחסרונות של Heapsort בהשוואה לאלגוריתמי מיון אחרים כמו Mergesort או Quicksort, במיוחד בהקשר של סיבוכיות מקום ויציבות?

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

• הגדרת ערימה: עץ בינארי מלא ותכונת הערימה (מקסימום/מינימום).
• ייצוג ערימה: שימוש במערך, חישוב אינדקסים (ילד שמאל: 2i+1, ימין: 2i+2, הורה: (i-1)/2).
• תור קדימויות: הגדרה וכיצד ערימה מממשת אותו ביעילות.
• פעולות ערימה: הכנסה (heapify-up), שליפה (heapify-down), בניית ערימה.
• סיבוכיות פעולות: הכנסה/שליפה O(log n), בניית ערימה O(n), הצצה O(1).
• אלגוריתם Heapsort: שלבי בניית ערימה ושליפה חוזרת.
• סיבוכיות Heapsort: זמן O(n log n) במקרה הגרוע, מקום O(1).
• השוואות: יתרונות וחסרונות Heapsort (in-place, לא יציב) מול אחרים.