מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/אופטימיזציית פעולה יחידה מממשק תור קדימויות/שאלה
מראה
באפליקציה מסויימת, יש צורך במבנה נתונים התומך בפעולות Insert(pq, v)
, Delete-Min(pq)
, וMin(pq)
. משמעות פעולות אלו היא בדיוק זו של תור קדימויות - מדובר במבנה נתונים המשתמש באיזושהי השוואה כדי לספק את האיבר הקטן בכל עת.
- ידוע שבאפליקציה זו, מספר הפעולות הצפוי מסוג
Delete-Min(pq)
וMin(pq)
הוא זניח יחסית למספר הפעולות הצפוי מסוגInsert(pq, v)
. אנא הצע מימוש כך שInsert(pq, v)
יהיה יעיל ככל האפשר. מה סיבוכיות שתי הפעולות האחרות במימוש שהצעת? - האם ייתכן מימוש לתור קדימויות בו הן
Insert(pq, v)
והןDelete-Min(pq)
יעבדו בזמן ?
שימו לב: #בסעיף הראשון, עליך למצוא יעיל ככל האפשר לInsert(pq, v) . אין צורך למצוא מימוש יעיל במיוחד לשתי הפעולות האחרות.
|