דף 1 מתוך 2

ערימות מינימום ומקסימום

נשלח: 09:08 26/06/2009
על ידי אבי
בוקר טוב,
מכמה אנשים הבנתי שעבור חלק א' של העבודה לא מספיק להתשמש ב k ערימות מקסימום אלא יש גם להשתמש בk ערימות מינימום .
מישהו יכול להסביר לי למה אני צריך גם k ערימות מינימום ? איזה בעיה הוא עוזר לי לפתור?

נשלח: 12:52 26/06/2009
על ידי sabagn
הם יעזרו לך לפתור את הבעייה שנוצרת לך לאחר פעולת insert
לאחר כל הכנסה הערימות שלך ישתנו ותצטרך לעשות איזון
בין הערימות.. האיזון מתבטא בזה שתצטרך להעביר לפעמים את האיבר המקסימלי
מערימה לערימה ולפעמים את האיבר המינימלי.

נשלח: 19:49 26/06/2009
על ידי ayeletd
היי,

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

תודה בכל מקרה

נשלח: 20:02 26/06/2009
על ידי gata
אתם רוצים להסביר למה אתם צריכים K ערימות מינימום וK ערימות מקסימום?!?!
זה לא קצת Space Waste?

נשלח: 21:35 26/06/2009
על ידי sabagn
אנחנו הרי צריכים להחזיר בסופו של דבר k מספרים מתוך המערך
בשביל זה אנחנו בונים k ערימות מקסימום כך שנוכל להחזיר בO(1) את השורש מכל ערימה
הבעיה היא כאשר אנחנו מכניסים איברים נוספים אחרי פעולת האיתחול,
הערימות שלנו משתנות והשורשים שלהם הם כבר לא האיברים שאנחנו צריכים להחזיר,
לכן אנחנו צריכים להעביר איברים מערימה לערימה. פעם נצטרך להעביר את האיבר המקסימלי לערימה מצד ימין ופעם את האיבר המינימלי לערימה מצד שמאל.
מכיוון שחוץ מלשורש בערימה אין לנו גישה ישירה לשום איבר אנחנו בונים עוד k ערימות מינימום
כדי שנוכל לגשת לאיברים האלה ולהעביר אותם.

נשלח: 01:06 27/06/2009
על ידי gata
תראו. אם יהיה לכם אלגוריתם שפועל בk*log(k)
או (k)
זה שקול ל O(1)
מכיוון של K קבוע כלשהו...
.
.
.
.
דבר שני לבנות k ערימות ולהחזיק אותם בו זמניות בכל עת (אם הבנתי נכון זה לא k ערימות אלא n
בכדי שיהיה אפשר לשלוף איבר כלשהו בכל זמן נתון) בקיצור זה גם מלא זכרון וגם מלא זמן לבנות את כל העסק
מצטער על הסגנון אבל קשה להתבטא כששיכורים :)
בקיצור זה לא נראה לי הכיוון.

נשלח: 11:49 27/06/2009
על ידי pavelger
אני צריך עזרה ביישום ההכנסה ב 2k הערימות

כרגע התוכנית שלי בנויה כך שהערימות מינינום ומקסימום שלי מקבילות אחת לשנייה כלומר כל האיברים שנמצאים בערימה המינימלית ה-i נמצאים גם בערימה המקסימלית ה-i אבל זה יוצר לי בעיה בהכנסה, כי אם לדוגמא אני רוצה להעביר את האיבר המינימאלי מהערימה ה-2 לראשונה זה צריך להיעשות גם בערימות המינימליות וגם במקסימאליות. להוציא את המינימאלי מהערימה המינ' השנייה זה פשוט וכך גם להכניס אותו אח"כ לערימה המקס' והמינ' הראשונה אבל צריך גם להוציא את האיבר מהערימה המקס' השנייה וזה בעיתי כי צריך לחפש את האיבר בערימה וזה כבר יהיה O(n.
האם יש למישהו רעיון איך לפתור את זה???

נשלח: 12:17 27/06/2009
על ידי sabagn
כן.. מכיוון שיש לך אותם איברים בכל 2 ערימות מקבילות
אתה צריך ליצור מצביעים בין כל איבר ואיבר ואז בקלות אתה יכול להעביר את אותו איבר ב(1)O

נשלח: 14:16 27/06/2009
על ידי roni
כן זה בדיוק החלק שנתקענו בו
איך עושים מצביעים בין 2 int או בין 2 Integer ?

נשלח: 21:16 28/06/2009
על ידי nettaka
איך אתם מתמודדים עם זה שהערימות בגדלים שונים, והגדלים משתנים עם כל שינוי של n?

נשלח: 23:44 28/06/2009
על ידי YossiCo
gata כתב:תראו. אם יהיה לכם אלגוריתם שפועל בk*log(k)
או (k)
זה שקול ל O(1)
מכיוון של K קבוע כלשהו...
.
.
.
.
דבר שני לבנות k ערימות ולהחזיק אותם בו זמניות בכל עת (אם הבנתי נכון זה לא k ערימות אלא n
בכדי שיהיה אפשר לשלוף איבר כלשהו בכל זמן נתון) בקיצור זה גם מלא זכרון וגם מלא זמן לבנות את כל העסק
מצטער על הסגנון אבל קשה להתבטא כששיכורים :)
בקיצור זה לא נראה לי הכיוון.
היי
אחד הדברים שחוזרים על עצמם בקורס הזה זה שאם רוצים לחסוך בזמן זה יעלה לנו בזכרון, ואם רוצים לחסוך בזכרון זה יעלה לנו בזמן...
...זה שזה מלא זמן לבנות את כל העסק - זה כנראה אחד מההשגים הנדרשים בעבודה הזו...

נשלח: 23:47 28/06/2009
על ידי YossiCo
nettaka כתב:איך אתם מתמודדים עם זה שהערימות בגדלים שונים, והגדלים משתנים עם כל שינוי של n?
הערימות לא אמורות להיות בגדלים שונים כי יש להם את אותם האיברים. כן תצטרכי לטפל בעדכון המצביעים בין הערימות במקרים של הוספה, והסרה של איברים.

נשלח: 00:03 29/06/2009
על ידי reneet
אם לוקחים n=22 k=3 יוצא שהערמה הראשונה בגודל 8 השניה הגודל 7 והשלישית גם 7 זה הגיוני?

נשלח: 00:04 29/06/2009
על ידי nettaka
אני לא מדברת על ערימות מקסימום ומינימום (על אף שזו הכותרת..), אלא על הערימות בחלוקה של כל הn איברים ל-K ערימות - הגדלים שלהן לא שווים. בהכנסה של איבר חדש לכל ערימה יש גודל לפי החישוב עם ה-n החדש, וצריך להתחשב בזה כשמעבירים מערימה לערימה.
אז איך עושים את זה?...

נשלח: 10:46 29/06/2009
על ידי orankap
העלו פה בפורום שבמקום מערכים רגילים עם פונייטרים (ערימה רגילה) כדאי להשתמש בוקטורים, שאלה בעצם מערכים דינמיים, כך שאין בעיה להכניס אינסוף איברים, הוקטור פשוט מגדיל את עצמו לבד. בקשר לגודל הקלט בערימה מסויימת, אנחנו שומרים מערך של קאונטרים בגודל k שמתעדכן עם כל שינוי/איזון.