החזרת מקסימום ב-O(1 במערכת עם מחיקה

[immortalus]

החזרת מקסימום ב-O(1 במערכת עם מחיקה

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

 

[vinney]

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

 

[immortalus]

זה בעיתי בשבילי כי המחיקה ב-O(logn

אני צריך שהכל (הכנסה, עדכון, ומחיקה) יוכלו להעשות ב-O(1

 

[HaifaMan]

HashTable

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

 

[vicz]

המממ

אפילו מיון ישיר לא מקיים את זה כי במקרה של מחיקת מקסימום יש לחפש מקסימום חדש. בדר"כ ניתן להגיע ליעילות גבוהה במיוחד בפעולות מסוימות ע"י הכנה מוקדמת בפעולות אחרות. במקרה כזה אף פעולה לא יכולה לקחת על עצמה הכנה כזו....

 

[immortalus]

המ.. כעקרון המבנה דורש הכנסה והוצאה ב

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

 

[vicz]

זמן קבוע בממוצע הוא תמיד רמז עבה ל-hash

(מתרגמים את זה "טבלאות ערבול"? ) נשאר רק לחשוב על המקסימום.... מה עשית עם מחסנית?

 

[immortalus]

חשבתי על ניהול של מחסנית מקסימום

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

 

[vicz]

גם אני חשבתי על כך שכל איבר יחזיק

את הקודם. וזה עובד יפה כשאני מוסיפה את האיבר המקסימלי. נניח שהמקסימום שלי כעת הוא 7. אם אני מוסיפה את 8, הרי שאני מעדכנת ש-7 קודם לו ואם 8 נמחק בהמשך, אז 7 תופס את מקומו כמקסימום. הבעיה היא מה קורה כאשר אחר כך אני מוסיפה 3? אולי בבוקר אני אהיה יותר חכמה...

 

[immortalus]

גם את במבני נתונים בטכניון?

כי נשמע כאילו את ממש מכירה את השאלה עצמה....

 

[HaifaMan]

אין עוד דרישות?

כל מבנה נתונים בסיסי יהיה טוב כל עוד תמיד תשמור מצביע לאיבר המכסימלי (אפילו עם מערך אפשר לממש את זה...). הדרך המסודרת יותר תהיה כמובן ערימת מכסימום כמו שצוין.

 

[immortalus]

אם למישהו עלה רעיון, השאלה עדין רלבנטית

אשמח לקצת עזרה....

 

[W12X]

לשמור את אבר המקסימום בצד

(בנוסף למ שהועלה) וכל פעם שאתה מוחק איבר לבדוק: אם האיבר שאתה מוחק הוא המקסימום לך לאיבר הקודם ואם לא לא לשנות

 

[HaifaMan]

ואם מחקת איבר שהוא לא המכסימום?

והוא נגיד השני בגודלו? מה תעשה אם אח"כ תמחק את המכסימום? איך תדע ללכת לאיבר השלישי ולא לשני?

 

[immortalus]

הסתדרתי + סליחה

אוקי.. אז קודם כל תודה על העזרה (או הנסיונות), הסתדרתי... במקרה השמטתי פרט חשוב שנראה לי שולי בזמנו עד שחשבתי עליו לעומק: האיברים יכולים להשתנו רק ב +/- 1, מה שבעצם בדיעבד מוסיף די הרבה (הרי אפשר לבדוק האם קיים איבר מקסימאלי נוסף ב-O(1 בממוצע...) בכל מקרה, תודה על תשומת הלב