מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/אופטימיזציית פעולה יחידה מממשק תור קדימויות/שאלה

באפליקציה מסויימת, יש צורך במבנה נתונים התומך בפעולות Insert(pq, v),‏ Delete-Min(pq),‏ וMin(pq).‏ משמעות פעולות אלו היא בדיוק זו של תור קדימויות - מדובר במבנה נתונים המשתמש באיזושהי השוואה כדי לספק את האיבר הקטן בכל עת.

1. ידוע שבאפליקציה זו, מספר הפעולות הצפוי מסוג Delete-Min(pq) וMin(pq) הוא זניח יחסית למספר הפעולות הצפוי מסוג Insert(pq, v).‏ אנא הצע מימוש כך שInsert(pq, v) יהיה יעיל ככל האפשר. מה סיבוכיות שתי הפעולות האחרות במימוש שהצעת?
2. האם ייתכן מימוש לתור קדימויות בו הן Insert(pq, v) והן Delete-Min(pq) יעבדו בזמן $\displaystyle O(1)$?

שימו לב: #בסעיף הראשון, עליך למצוא יעיל ככל האפשר לInsert(pq, v). אין צורך למצוא מימוש יעיל במיוחד לשתי הפעולות האחרות. אפשר לפתור את הסעיף השני גם מבלי לפתור את הסעיף הראשון.