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