נושא: ערימות

נשלח בתאריך: 02 July 2005 בשעה 23:50 | IP רשוּם

שלום רב, השאלה שלי היא:

נתונה ערימה H בת N אברים:

א) נניח שבוחרים מסלול מהשורש עד לאחד העלים ומגדילים את כל המפתחות במסלול זה בערך כלשהו c>0, יש לתאר אלגוריתם לתיקום הערמה בזמן O(loglogN.

ב) נניח שבוחרים logN איברים כלשהם בערימה ומגדילים את כל המפתחות שלהם בערך כלשהו C>0, האם עדיין ניתן לתקן את הערימה בסיבוכיות של סעיף א? הוכיחו או הפריכו.

אשמח לעזרה של כל מי שיודע איך לפתור את זה, אני מקווה שזה יהיה מהר כי זו שאלה לקראת מבחן, בתודה רבה

רון

נשלח בתאריך: 03 July 2005 בשעה 09:52 | IP רשוּם

אני מצטער, הייתה לי טעות בשאלה, הסיבוכיות הנדרשת היא log^2 של N, לא

log(logN, שמתי לב אחר-כך שזה לא אותו הדבר.

רון