Description

יש לקרוא היטב לפני תחילת העבודה!
מבוא:
במעבדה הנוכחית נממש תור עדיפויות בעזרת ערימה בינארית. את הערימה נממש באמצעות מערך.
תיאור:
ביישומים רבים יש צורך בניהול תור שהוצאת האיברים ממנו תהיה על בסיס של עדיפות. במקרים כאלהתור רגיל לא פותר את הבעיה ביעילות. שימוש ידוע מאוד בתור עדיפויות הוא האלגוריתם של דייקסטרהלמציאת מסלול קל ביותר בגרף עם קשתות ממושקלות.
הגדרה 1 (תור עדיפויות):
תור עדיפויות הוא מבנה התומך לפחות בשתי הפעולות הבאות:
insert מכניס איבר למבנה
deleteMin מוצא, מוחק ומחזיר את האיבר המינימאלי במבנה.
מימושים אפשריים של תור עדיפויות:
– רשימה מקושרת: זמן הכנסה (1)O ; זמן ליניארי למחיקת המינימום.
– רשימה מקושרת ממוינת: זמן ליניארי להכנסה וזמן קבוע להוצאה.
– עץ חיפוש מאוזן נותן (O(logN לשתי הפעולות, אך שימוש בעץ חיפוש הוא יותר ממה שצריך.
נראה מימוש פשוט הנותן הכנסה בזמן לוגריתמי, מחיקה בזמן לוגריתמי, ובנייה בזמן לינארי. מימוש זה הוא ערימה(heap). הערה: מימוש ע״י ערימה יעיל יותר עבור תור עדיפויות בהיותו ייעודי לבעיה זו, ולכן מאפשר פעולות נוספותבזמן ריצה קצר, למשל, מציאת מינימום בזמן (O(1.
הגדר2 (ערימה ):
ערימה היא עץ בינארי המקיים שני תנאים:
תנאי מבני: העץ צריך להיות כמעט שלם
תנאי סדר: לכל צומתX בעץ, המפתח של ההורה שלX קטן או שווה מהמפתח שלX
עץ כמעט שלם (complete) הוא עץ מלא פרט אולי לרמה התחתונה, שממולאת משמאל לימין.
.מספר הצמתים בעץ שלם בגובהh נע בתחום: 1 − 1+ℎ −−− 2ℎ2 לכן הגובה הוא (θ(𝑙𝑜𝑔 𝑁.
תכונת הסדר מבטיחה שמפתח של השורש הוא קטן ביותר, ולכן מציאת המינימום היא בזמן קבוע.
מימוש הערמה:
הימני במיקום 1 +𝑖 2. מצד שני, מיקום האב לבן הנמצא במקוםi יהיה במקום ה- ⌋2/𝑖 .⌊𝑖2אפשר לאחסן ערמה במערך, רמה אחרי רמה, החל ממיקום 1. לכל מיקוםi במערך, הבן השמאלי הוא במיקום , והבן
למשל, העץ הבינארי הבא יוחזק כמערך כדלהלן:

0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G H I
הערה: שימו לב, כי המקום ה-0 במערך לא מכיל נתונים של הערימה.
1) השלימו את המחלקהMinHeap הגנרית
– עם פרמטר שהוא טיפוס המממש את הממשקComparable
– עם שני בנאים
MinHeap(int), MinHeap(T[])
– .isFull, isEmpty, insert, getMin, deleteMin, toString והשיטו
– כדי ליצור מערך חדש מטיפוס גנריT בשםdata למשל, יש לבצע זאת בצורה הבאה:
data = (T[]) new Comparable[size]; .שורת קוד זו יוצרת ״הערת אזהרה״
כדי שהקומפיילר לא יתייחס לאזהרה זו, ניתן לכתוב מעליה:
@SuppressWarnings(“unchecked”)
אם עדיין יש אזהרה בבודק האוטומטי – ניתן להחליף שורה זו בשורה הבאה:
@SuppressWarnings({“unchecked”,”rawtypes”})
אחד הבנאים יוצר ערימה ריקה בגודל נתון, והשני יוצר ערימה המכילה את כל איברי המערך הנתון.
insert: האיבר החדש ייכנס למקום הבא במערך, ואחר כך יפעפע למעלה כמה שצריך.
delMin: מביאים את האיבר במקום האחרון למקום הראשון (לשורש), ואחר כך יפעפע למטה כמה שצריך.
יש קובץ נוסף בMOODLE עם הסבר יותר מפורט על הכנסה ומחיקה.
הערה: אם הערימה ריקה, אזdeleteMin תחזירnull , ו-getMin תזרוק חריגה.
2) הוסיפו למחלקהPerson , כך שהיא תממש את הממשקComparable כאשר ההשוואה היא על פיid בלבד.
המשימה היא לגרום למחלקת הבדיקהHeapTest להתקמפל ולעבוד בצורה תקינה.
עבודה נעימה!!!
סדר העבודה ופרטים טכניים
● שליפת הפרויקטDS-Lab10-MinHeap מתוךGITHUB בקישור:
https://github.com/ykanizo/DSLab2022-2023Public
○ אם אין לכם גישה לפרויקט שהורדתם מGITHUB במעבדות הקודמות יש לבצע שליפהמחדש.
○ אם יש לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הראשונה אז בצעו:
■ קליק על שם הפרויקט.
■ עכבר ימני
Team–>Pull ■ File–>Import->Git->Projects From Git->Existing Local Repository ■
פורמט קובץ ההגשה ובדיקתו:
בשםZIP פורמט : יש להגיש קובץ43_lab10_123456789_987654321.zip
(כמובן, יש להחליף את המספרים עם מספרי ת.ז. של המגישים).
על הקובץ להכיל את כל קבצי הJAVA שכתבתם כאשר הם נמצאים בתתי תיקיות בתוך התיקייה
il/ac/telhai/ds/על פי המבנה של הפרוייקט הנתון.
כלומר, השורש של קובץ ההגשה יכיל רק תיקייה בשםil , והוא יכיל את כל קבצי -java על פיהתבנית הנתונה בפרוייקט.
להמחשה תמונה של קובץ כזה שנפתח ב -WindowsExplorer

בדיקת קובץ ההגשה: בדקו את הקובץ שיצרתם בתוכנת הבדיקה בקישור:
https://csweb.telhai.ac.il/ראו סרטון הדגמה של השימוש בתוכנת הבדיקה.
חשוב!!!
בדיקת ההגשות תבוצע ברובה ע”י תוכנית הבדיקה האוטומטית הנ”ל. תוצאת הבדיקה תהייהבעיקרון זהה לתוצאת הבדיקה הנ”ל שאתם אמורים לערוך בעצמכם . כלומר, אם ביצעתם אתהבדיקה באתר החוג, לא תקבלו הפתעות בדיעבד. אחרת, ייתכן שתרגיל שעבדתם עליו קשהייפסל בגלל פורמט הגשה שגוי וכו.’ דבר שהיה ניתן לתקנו בקלות אם הייתם מבצעים את הבדיקה.
היות ואין הפתעות בדיעבד, לא תינתן אפשרות של תיקונים, הגשות חוזרות וכד.’הגשה שלא מגיעה לשלב הקומפילציה תקבל ציון 0.
הגשה שלא מתקמפלת תקבל ציון נמוך מ- 40 לפי סוג הבעיה.
הגשה שמתקמפלת תקבל ציון 40 ומעלה בהתאם לתוצאות הריצה, ותוצאת הבדיקה הידנית שלהקוד (חוץ ממקרה של העתקה).
תכנית הבדיקה האוטומטית מכילה תוכנה חכמה המגלה העתקות. מקרים של העתקות יטופלובחומרה