מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/Heapsort/תשובה

גרסה עם Build-Heap

1. קל לראות שהאלגוריתם עובד: כפי שראינו בבניית ערימה בינרית ממערך, Build-Heap מייצרת ערימה תקינה ממערך, והרי Delete-Min מוציאה ומחזירה את האיבר הקטן ביותר.
2. הסיבוכיות היא $\displaystyle \Theta (n\cdot \log(n))$ במקרה הגרוע. ראינו מימוש לBuild-Heap שעובד בזמן $\displaystyle \Theta (n)$,‏ ואנו יודעים שסיבוכיות Delete-Min על ערימה בת $\displaystyle i$ איברים היא $\displaystyle \Theta (\log(i))$ במקרה הגרוע. סיבוכיות הלולאה 3-4, לכן, היא $\displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))$ (ראה גם טורים שימושיים בסדרי גדילה).

גרסה עם סדרת פעולות Insert

1. אין שינוי בנכונות, כי הלולאה 3-4 גם כן מייצרת ערימה תקינה מהמערך, ואין הבדל מנקודה זו.
2. אף הסיבוכיות אינה שונה, מפני שבמקום הביטוי $\displaystyle \Theta (n)+\Theta (n\cdot \log(n))$ (בסעיף הקודם), נקבל כעת $\displaystyle \Theta (n\cdot \log(n))+\Theta (n\cdot \log(n))$. שני הביטויים שקולים (מבחינת סדרי הגדילה).