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

נתון תור קדימויות $Q$ שבאמצעותו ניתן לבצע את שתי הפעולות INSERT (הכנסת איבר) ו-EXTRACT-MAX (מחיקת המקסימום). לא נתון כיצד תור זה ממומש. הוכיחו שחייבת להיות לפחות סדרה אחת של $n$ פעולות INSERT ו-EXTRACT-MAX (בסדר כלשהו), כך שלפחות אחת הפעולות מתבצעת בזמן $\Omega(\lg n)$.

רמז: הראו שאם שתי הפעולות רצות בזמן $o(\lg n)$, ניתן למיין $n$ מספרים בזמן $o(n \lg n)$, בסתירה לחסם התחתון של מיון מבוסס השוואות.

פתרון: **הוכחה בשיטת הרדוקציה (הוכחה בשלילה):** נניח בשלילה ששתי הפעולות INSERT ו-EXTRACT-MAX מתבצעות תמיד בזמן $o(\lg n)$ (כלומר, בזמן קטן ממש מ-$\lg n$ אסימפטוטית). נבנה אלגוריתם מיון: 1. בהינתן מערך $A[1..n]$, נכניס את כל $n$ האיברים ל-$Q$ באמצעות $n$ פעולות INSERT. 2. נבצע $n$ פעולות EXTRACT-MAX ונכניס את התוצאות למערך מהסוף להתחלה. אלגוריתם זה ממיין את המערך. **ניתוח זמן:** - שלב 1: $n$ פעולות INSERT, כל אחת $o(\lg n)$, סה"כ $o(n \lg n)$. - שלב 2: $n$ פעולות EXTRACT-MAX, כל אחת $o(\lg n)$, סה"כ $o(n \lg n)$. - זמן כולל: $o(n \lg n)$. אבל ידוע שהחסם התחתון למיון מבוסס השוואות הוא $\Omega(n \lg n)$. קיבלנו סתירה. לכן, חייבת להיות לפחות סדרה אחת של $n$ פעולות שבה לפחות אחת מהפעולות מתבצעת בזמן $\Omega(\lg n)$. $\blacksquare$