תכנון מבנה נתונים יעיל

לפניך הגדרה של חמש פעולות הפועלות על מבנה נתונים כלשהו. שים לב: שמות הפעולות שלפניך אינם כתובים ב-Java או ב-C#.

• insert(x): פעולה המכניסה למבנה איבר שערכו X מטיפוס שלם.
• showMin(): פעולה המחזירה את הערך הנמוך ביותר במבנה, בלי לשנות את המבנה.
• getMax(): פעולה המחזירה את האיבר שערכו הוא הגדול ביותר במבנה, ומוציאה אותו מן המבנה. אם יש יותר מאיבר אחד כזה, הפעולה תחזיר ותוציא את זה שמופיע ראשון.
• exists(x): פעולה בוליאנית המחזירה true אם האיבר שערכו x קיים במבנה. אחרת הפעולה מחזירה false.
• div7(): פעולה בוליאנית המחזירה true אם קיים במבנה איבר שערכו מתחלק ב-7 בלי שארית. אחרת הפעולה מחזירה false.

נרצה להציע מבני נתונים העומדים בדרישות סיבוכיות שונות למימוש פעולות מתוך חמש הפעולות שהוגדרו. דוגמה: רוצים להציע מבנה נתונים שאפשר לבצע עליו את הפעולות showMin, insert בסיבוכיות O(1), ואת הפעולות exists, getMax בסיבוכיות O(n). לשם כך נגדיר את מבנה הנתונים ונסביר כיצד ימומשו הפעולות. שים לב: במבנה זה אין צורך להתייחס לפעולה div7.

מבנה נתונים מתאים מורכב מ-:

• רשימה מקושרת דו כיוונית, lst מטיפוס שלם.
• מצביע על האיבר המינימלי שהוכנס לרשימה, min.

הפעולות יבוצעו כך:

• insert(x): הכנסת האיבר x לראש הרשימה. אם האיבר קטן מן המינימום עד כה, עדכון המצביע min כך שיצביע על האיבר החדש.
  • נימוק: הכנסת איבר לראש הרשימה - O(1). אם הוכנס איבר שקטן מן המינימום: עדכון המצביע לאיבר המינימלי - O(1). אם הוכנס איבר ראשון הכנסה לראש הרשימה ב-O(1) ועדכון המצביע לאיבר הראשון שהוא גם המינימלי. סך הכול - O(1).
• showMin(): החזרת הערך של האיבר שעליו מצביע min.
  • נימוק: החזרת הערך - O(1).
• exists(x): מעבר על הרשימה lst וחיפוש האיבר שערכו x.
  • נימוק: במקרה הגרוע מעבר על כל הרשימה - O(n).
• getMax(): מעבר על הרשימה lst, חיפוש האיבר שערכו מקסימלי והוצאתו מן הרשימה.
  • נימוק: חיפוש האיבר שערכו מקסימלי O(n). הוצאתו מן הרשימה O(1).