../images/Emo119.gifמיזוג ערמות הבנויות באמצעות מצביעים
נתונה לי ערמה (heap) שלמה הממומשת באמצעות מצביעים (כעץ), ולא כמערך, וגובהה h. נבחר מסלול כלשהו x_0,x_1,...,x_h מהשורש x_0 ועד עלה x_h, וכל הצמתים במסלול נמחקו. בכך הערמה התפצלה ל-h ערמות B_0,B_1,...,B_h-1, כאשר גובה הערמה ה-i הוא i. אני צריך למצוא אלגוריתם למיזוג h הערימות הללו בזמן (O(lg^2 n, כדי ליצור ערמה הממומשת באמצעות מצביעים ומכילה את כל הצמתים ב-h הערמות. חשבתי על השאלה הזאת כבר ימים, והגעתי למספר מסקנות:
אפשר להניח בלי הגבלת הכלליות שהמסלול שנמחק הוא כולו ימני (כלומר, x_i+1 הוא הבן הימני של x_i לכל i), לשם פשטות.
אם נסמן ב-y_i את האח של x_i (כלומר, במקרה שלנו, הבן השמאלי של אביו), אז שורש הערמה החדשה חייב להיות {max{y_i | i=1,...,h.
כאשר בוחרים את אותו מקסימום, אפשר להחליף אותו ב-y_h (אשר הוא צומת בודד), ולבצע Heapify כדי לשמור על מבנה הערימה.
הבן השמאלי של השורש יהיה y_1, והגובה של הערמה המושרשת בו הוא h-1, אז הוא מספיק.
הבן הימני של השורש יצטרך להיות המקסימום של ה-y_i-ים שנשארו, אבל אני לא יודע במה להחליף אותו כי הצומת הבודד (y_h) כבר נלקח.
הערימה שתתקבל בסופו של דבר תהיה בגובה h אף היא, אבל נצטרך "לגנוב" עלים מימין למטה, כי מספר הצמתים שנותרו הוא:
נתונה לי ערמה (heap) שלמה הממומשת באמצעות מצביעים (כעץ), ולא כמערך, וגובהה h. נבחר מסלול כלשהו x_0,x_1,...,x_h מהשורש x_0 ועד עלה x_h, וכל הצמתים במסלול נמחקו. בכך הערמה התפצלה ל-h ערמות B_0,B_1,...,B_h-1, כאשר גובה הערמה ה-i הוא i. אני צריך למצוא אלגוריתם למיזוג h הערימות הללו בזמן (O(lg^2 n, כדי ליצור ערמה הממומשת באמצעות מצביעים ומכילה את כל הצמתים ב-h הערמות. חשבתי על השאלה הזאת כבר ימים, והגעתי למספר מסקנות:
2^(h+1)-1-(h+1)
כאן נתקעתי, ואני לא יודע איך להמשיך. האם אני יכול לקבל הכוונה, בבקשה? תודה