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

מנהל: TA_Isana

אבי
הודעות: 7
הצטרף: 21:39 26/11/2008

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

שליחה על ידי אבי » 09:08 26/06/2009

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

sabagn
הודעות: 34
הצטרף: 16:51 19/11/2008

שליחה על ידי sabagn » 12:52 26/06/2009

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

ayeletd
הודעות: 27
הצטרף: 19:25 17/11/2008

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

היי,

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

תודה בכל מקרה
איילת

gata
הודעות: 88
הצטרף: 17:25 10/11/2007

שליחה על ידי gata » 20:02 26/06/2009

אתם רוצים להסביר למה אתם צריכים K ערימות מינימום וK ערימות מקסימום?!?!
זה לא קצת Space Waste?

sabagn
הודעות: 34
הצטרף: 16:51 19/11/2008

שליחה על ידי sabagn » 21:35 26/06/2009

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

gata
הודעות: 88
הצטרף: 17:25 10/11/2007

שליחה על ידי gata » 01:06 27/06/2009

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

pavelger
הודעות: 5
הצטרף: 21:20 22/12/2008

שליחה על ידי pavelger » 11:49 27/06/2009

אני צריך עזרה ביישום ההכנסה ב 2k הערימות

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

sabagn
הודעות: 34
הצטרף: 16:51 19/11/2008

שליחה על ידי sabagn » 12:17 27/06/2009

כן.. מכיוון שיש לך אותם איברים בכל 2 ערימות מקבילות
אתה צריך ליצור מצביעים בין כל איבר ואיבר ואז בקלות אתה יכול להעביר את אותו איבר ב(1)O

roni
הודעות: 38
הצטרף: 18:17 28/12/2008

שליחה על ידי roni » 14:16 27/06/2009

כן זה בדיוק החלק שנתקענו בו
איך עושים מצביעים בין 2 int או בין 2 Integer ?

nettaka
הודעות: 20
הצטרף: 00:29 10/12/2008

שליחה על ידי nettaka » 21:16 28/06/2009

איך אתם מתמודדים עם זה שהערימות בגדלים שונים, והגדלים משתנים עם כל שינוי של n?

YossiCo
הודעות: 24
הצטרף: 19:20 17/12/2008
מיקום: ממש פה קרוב...

שליחה על ידי YossiCo » 23:44 28/06/2009

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

YossiCo
הודעות: 24
הצטרף: 19:20 17/12/2008
מיקום: ממש פה קרוב...

שליחה על ידי YossiCo » 23:47 28/06/2009

nettaka כתב:איך אתם מתמודדים עם זה שהערימות בגדלים שונים, והגדלים משתנים עם כל שינוי של n?
הערימות לא אמורות להיות בגדלים שונים כי יש להם את אותם האיברים. כן תצטרכי לטפל בעדכון המצביעים בין הערימות במקרים של הוספה, והסרה של איברים.

reneet
הודעות: 7
הצטרף: 12:25 10/02/2009

שליחה על ידי reneet » 00:03 29/06/2009

אם לוקחים n=22 k=3 יוצא שהערמה הראשונה בגודל 8 השניה הגודל 7 והשלישית גם 7 זה הגיוני?

nettaka
הודעות: 20
הצטרף: 00:29 10/12/2008

שליחה על ידי nettaka » 00:04 29/06/2009

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

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

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

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

שלח תגובה

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