insert בחלק א

מנהל: TA_Isana

שלח תגובה
zahavl
הודעות: 31
הצטרף: 16:20 06/12/2008

insert בחלק א

שליחה על ידי zahavl » 23:27 28/06/2009

נתקעתי בשלב ההכנסה בחלק א.
האם מישהו יכול להסביר לי אחרי שאני מכניסה איבר לערימה המתאימה איך אני בודקת שהמצב לא "התקלקל" ואם הוא כן אז איך אני "מתקנת"?
אשמח לכל כיוון
תודה

orankap
הודעות: 67
הצטרף: 14:23 02/12/2008

שליחה על ידי orankap » 10:51 29/06/2009

לפני שאת מכניסה את צריכה לחשב את האיברים החדשים, אנחנו שומרים אותם במערך orders, עכשיו, יש לנו עוד מערך שבו יש את מספר האיברים בכל ערימה, צריך להשוות בין המערכים תוך כדאי חיפוש מיקום האיבר החדש (קטן מהכי גדול או גדול מההכי קטן) ואז לעדכן בהתאם.
יכול להיות מקרה של 6 ערימות, שבהכנסת איבר מסויים תצטרכי לעדכן את ערימות 2 4 5 6, זה מאוד דינמי ותלוי במספר האיברים ברגע נתון.

נ.ב:
אנחנו רק בשלב התאוריה אז קחי את כל מה שרשמתי בעירבון מוגבל :oops:

candle of god
הודעות: 15
הצטרף: 21:43 01/12/2008

הנה מעט עזרה בנושא

שליחה על ידי candle of god » 15:17 29/06/2009

בנוגע להכנסה עצמה - אני מבין שמדובר במקרה שבו יש לך ערימה אחת, כלומר - התכלס, אחרי שהוחלט לאיזו ערימה מתוך K הערימות יכנס האיבר המדובר- איך תכלס מכניסים איבר לערימה.
אז הדרך הכי ישירה זה (בהנחה שהבסיס של הערימה זה מערך) להוסיף את האיבר בסוף המערך ואז לבנות את הערימה מחדש מהמערך החדש, כפי שנבנתה מלכתחילה.... זה יצא נכון - אבל לבנות ערימה זה On ולא logn. לכן צריך לחשוב על איך להכניס את האיבר לערימה בלי לחרבש הכל ולבנות מחדש.
אז עיקר הרעיון הוא להכניס את האיבר לסוף המערך. עכשיו האיבר הוא עלה כלשהו. אחר כך לדאוג להשוואתו לאבא שלו ולהחליף ביניהם אם צריך. אם היה צריך חילוף אז להשוות גם לסבא שלו, ואם גם פה היה צריך חילוף אז לסבא-רבא וכן הלאה. ברגע שלא צריך חילוף נוסף עוצרים.
נניח אנחנו בערימת מקסימום בשביל ההסבר. כל מי שבתת העץ הימני או השמאלי של האיבר שהכנסנו הוא קטן ממנו: כי אם יש לו בנים, אז הגדול מבינהם הוא זה שלפני ההחלפה היה ההורה של האיבר, והוא הרי התחלף עם האיבר- כלומר קטן ממנו.

בכיף לשאול עוד אם משהו לא מובן. בהצלחה.

שלח תגובה

חזור אל “- מבני נתונים”