שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2018 - ערימות

קבעו אם הטענה הבאה נכונה או לא והסבירו בקצרה (2-3 שורות): ניתן לבנות ערימה בזמן לינארי.

רמז: חשבו על האלגוריתם BUILD-HEAP שמשתמש ב-heapify מלמטה למעלה.

פתרון: **נכון.** אלגוריתם BUILD-HEAP בונה ערימה ע"י הפעלת heapify על כל צומת פנימי מלמטה למעלה. הניתוח מראה שהסיבוכיות היא $O(n)$, כי רוב הצמתים נמצאים בגבהים נמוכים: $\sum_{h=0}^{\lfloor \log n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil \cdot O(h) = O(n \sum_{h=0}^{\infty} \frac{h}{2^h}) = O(n)$.