מבנה נתונים

[carlos22]

מבנה נתונים

לא הצלחתי להבין איך אני משלב מבנה של min heap בתרגיל. הכוונה להעביר את כל הרשומות מהרשימות לערימה ולמיין מיון ערימה ?

 

[vicz]

קצת חסר המידע על התרגיל עצמו,אבל באופן כללי

למרות שמציירים ערימה כעץ, ערימה היא בעצם מערך שהאיברים בו מסודרים כך שהם שומרים על תכונת הערימה בהינתן מערך כלשהו, ניתן להפוך אותו לערימה ע"י שגרה לבניית ערימה מיון ערימה ניתן להפעיל על מערך שהוא כבר ערימה אם תתן לי עוד פרטים על התרגיל אולי אוכל לעזור עוד

 

[carlos22]

חשבתי

שצירפתי את הקובץ ..

 

[HaifaMan]

הרעיון שלי

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