הרצאה 3 - Priority Queue (Heap) Complexity Analysis

תוכן עניינים

תזכורת: Binary Heap ופעולותיו
מה חסר? בניית Heap מ-N איברים
NaïveBuildHeap - O(n log n)
BuildHeap יעיל Bottom-Up
הוכחת נכונות באינדוקציה הפוכה
ניתוח סיבוכיות O(n)
סיכום

1. תזכורת: Binary Heap

Priority Queue ADT

קבוצת איברים, לכל אחד עדיפות (key). פעולות: \(\text{insert}(x,k)\), \(\text{find-min}()\), \(\text{delete-min}()\), \(\text{decrease-key}(x,k)\).

Binary Heap

עץ בינארי כמעט שלם, מקיים את תכונת ה-Heap (Min-Heap: שום צומת לא גדול מילדיו). מימוש מקובל: מערך — צומת באינדקס \(i\), ילדיו ב-\(2i\) ו-\(2i+1\).

פעולה	סיבוכיות
FindMin	\(O(1)\)
DeleteMin	\(O(\log n)\)
Insert	\(O(\log n)\)
DecreaseKey	\(O(\log n)\)
מקום	מערך בגודל \(N\) + משתנה גודל \(O(N)\)

2. מה חסר?

עדיין לא הראינו איך לבנות Heap מ-\(N\) איברים נתונים. שתי אפשרויות:

NaïveBuildHeap: \(n\) פעמים Insert עם PercUp.
BuildHeap יעיל: PercDown מלמטה למעלה.

3. NaïveBuildHeap - O(n log n)

אלגוריתם

NaïveBuildHeap(A, n):
  הקצה מערך B בגודל n
  for i = 1 to n:
    Insert(B, i, A[i])    // PercUp בכל הכנסה
  for i = 1 to n:
    A[i] = B[i]

סיבוכיות: \(O(n \log n)\)

\(n\) קריאות ל-Insert, כל אחת מבצעת PercUp בעלות פרופורציונלית לעומק העץ הנוכחי. אחרי \(n/2\) הכנסות, העומק הוא \(\log(n/2)\). \(n/2\) ההכנסות האחרונות עולות לפחות \(\frac{n}{2}\log\frac{n}{2} = \Omega(n \log n)\).
סה"כ: \(O(n \log n)\). נראה שאפשר לעשות טוב יותר!

4. BuildHeap יעיל - Bottom-Up

רעיון

הכנס את כל האיברים למערך בסדר שרירותי, ואז "תקן" את ה-Heap מלמטה למעלה ע"י PercDown. צמתים \(\lfloor n/2 \rfloor + 1\) עד \(n\) הם עלים — כבר מקיימים את תכונת ה-Heap.

BuildHeap(A):
  n ← length(A)
  for i = ⌊n/2⌋ downto 1:
    PercDown(i, A[i], n, A)

דוגמה: n = 11, A = [11,5,10,9,3,8,12,2,7,6,4]

מתחילים מ-\(i = 5\) (אינדקס אמצעי). PercDown על כל צומת מוריד אותו למקומו הנכון. אחרי \(i=1\) (השורש), כל המערך מקיים תכונת Heap.

5. הוכחת נכונות (אינדוקציה הפוכה)

טענה

אחרי טיפול ב-\(A[i]\), תת-המערך \(A[i..n]\) מקיים את תכונת ה-Heap.

בסיס (\(i = \lfloor n/2 \rfloor + 1\)): \(A[i..n]\) מכיל רק עלים — מקיים את התכונה ריק.

הנחה: אחרי טיפול ב-\(A[i+1]\), \(A[(i+1)..n]\) מקיים תכונת Heap.

צעד: עבור \(i \leq \lfloor n/2 \rfloor\), לפי הנחת האינדוקציה רק \(A[i]\) עצמו עלול לא לקיים את התכונה. אחרי PercDown(i), הוא מתוקן ⟹ \(A[i..n]\) מקיים תכונת Heap. ✓

6. ניתוח סיבוכיות - O(n)

תזכורת

צומת בגובה \(h\): PercDown לוקח \(O(h)\) זמן.

נניח עץ בינארי שלם בגובה \(k\): \(N = 2^{k+1} - 1\) איברים.

רמה	צעדים	מספר איברים
0 (שורש)	\(k\)	1
1	\(k-1\)	2
\(i\)	\(k-i\)	\(2^i\)
\(k\) (עלים)	0	\(2^k\)

\text{Total} = \sum_{i=0}^{k}(k-i) \cdot 2^i = 2^k \sum_{i=0}^{k} \dfrac{i}{2^i} \leq N \cdot \sum_{i=0}^{\infty} \dfrac{i}{2^i}

הטור \(\sum i/2^i\) הוא טור הנדסי-אריתמטי מתכנס. ניתן להראות:

\sum_{i=0}^{\infty} \dfrac{i}{2^i} \leq \sum_{i=0}^{\infty} \left(\dfrac{3}{4}\right)^i = \dfrac{1}{1 - 3/4} = 4

מסקנה

BuildHeap יעיל מסתכם ב-\(\leq 4N = O(N)\). BuildHeap בזמן ליניארי!
זה אפשרי גם כש-\(n\) קריאות ל-PercDown — כי רוב הצמתים נמצאים בעומק נמוך, ולא צריכים הרבה צעדים.

7. סיכום

NaïveBuildHeap: \(n\) Insert עם PercUp ⟹ \(O(n \log n)\). לא יעיל.
BuildHeap יעיל: PercDown מ-\(\lfloor n/2 \rfloor\) למטה ⟹ \(O(n)\) — ליניארי!
נכונות: אינדוקציה הפוכה. \(A[i..n]\) הופך ל-Heap אחרי הטיפול ב-\(i\).
ניתוח: \(\sum_{i=0}^{k}(k-i)\cdot 2^i \leq 4N = O(N)\). הטריק: רוב הצמתים בעומקים נמוכים.

משמעות מעשית

הפרש משמעותי! עבור \(n = 10^6\), \(O(n \log n)\) זה ~\(2 \cdot 10^7\) פעולות; \(O(n)\) זה ~\(10^6\) פעולות. פי 20 מהיר. זה מה שמאפשר HeapSort בתחילת הסיבוב במהירות.