שאלה במבוא לאלגוריתמים

[patch81]

שאלה במבוא לאלגוריתמים

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

 

[immortalus]

תוסיף לכל איבר שדה שזוכר את האיבר המינימאלי

אם נכנס איבר חדש שהוא המינימאלי, הוא יזכור את האיבר המינימאלי הקודם. אם האיבר המינימאלי נמחק, אתה משחזר את האיבר המינימאלי הקודם ששמור באיבר שנמחק זה עתה...

 

[patch81]

תודה

 

[patch81]

בעצם זה לא נכון.

דוגמה נגדית - 5,1,2 אמינימלי הקודם של 1 זה 5 ו 2 אף פעם לא היה מנימלי. לכן כשנוציא את 1 נקבל שהמינימלי הקודם זה 5 והוא באמת 2. אפשר להכניס את 2 למקומו הנכון אבל זה כבר insertion sort

 

[JohnnyPiloni]

אולי

תיצור מחסנית שאליה תכניס את המספרים בנוסף תיצור מערך של פוינטרים שיהיו מסודרים לפי סדר מינימלי לדוג נכניס את 5 למחסנית והמערך במקום הראשון יצביע עליו נכניס את 1 למחסנית והמערך במקום השני יצביע עליו ונבצע בדיקה במערך אם הפוינטר מתא השני מצביע לערך שקטן מהערך שבתא הראשון נעשה החלפה במקומות

 

[JohnnyPiloni]

במבט שני על השאלה

לא מבקשים ממך למחוק את האיבר המינמאלי רק להחזיר מינמאלי אז התשובה שלimmortalus טובה

 

[patch81]

צודק - מקרה הקצה שלי לא רלוונטי - תודה לשניכם

 

[Okuryo]

../images/Emo119.gifאני השתמשתי בשתי מחסניות:

מחסנית אחת לכל האיברים (נקרא לה S), ואחת לכל האיברים המינימליים (נקרא לה Sm): בכל פעם שמוסיפים איבר, דוחפים אותו ל-S, ואם הוא קטן מהראש של Sm, אז דוחפים אותו גם ל-Sm. כדי להחזיר את האיבר המינימלי פשוט מחזירים את הראש של Sm, וכשמוחקים את האיבר שהוכנס אחרון, עושים pop ל-S, וגם ל-Sm אם היה להן אותו ראש.

 

[uvdude]

זה לא עובד

אני חושב שגם לוגית זה פשוט לא נכון, ובכל מקרה יש לך בעיה עם איברים שחוזרים על עצמם. הפתרון הנכון הוא להשתמש במחסנית אחת שמחזיקה בתאים שלה גם את המפתח וגם את הערך המינימלי של תת-המחסנית שמתחתיה. אני מצרף דוגמה של מחסנית שאני בטוח שתבינו ממנה לבד את הרעיון. המפתח בצד ימין, הערך המינימלי השמור בצד שמאל: | 1 - 1 | | 2 - 2 | | 9 - 3 | | 8 - 3 | | 3 - 3 | | 6 - 5 | | 5 - 5 | _____ זה פותר הכל בזמן הנתון...

 

[Okuryo]

../images/Emo119.gifהפתרון עם השדה באמת פשוט יותר,

אבל מה הבעיה עם איברים שחוזרים על עצמם בפתרון שלי?