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

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