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