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

1. סעיף זה הוא טריביאלי. נשתמש ברשימה מקושרת דו-כוונית (ייתכנו מימושים אחרים, כמובן). Insert תקרא לInsert-Front של רשימה מקושרת, ותעבוד בזמן $\displaystyle O(1)$. את Min וDelete-Min נממש בעזרת לולאות על חוליות הרשימה. סיבוכיות כל אחת מפעולות אלה תהיה לינארית במספר החוליות במקרה הגרוע.
2. נזכר שבהנתן תור קדימויות, ניתן לממש בעזרת סידרת $\displaystyle n$ פעולות Insert ולאחריה סידרת $\displaystyle n$ פעולות Delete-Min (באופן כמעט זהה לHeapsort). לו כל פעולה היתה עובדת בזמן $\displaystyle O(1)$, אז ניתן היה למיין בזמן לינארי, בניגוד לחסם התחתון על מיון מבוסס-השוואות שלמדנו.