אלגוריתם של מיון ערימה

[lionsh]

אלגוריתם של מיון ערימה

שלום לכולם, נתקעתי בשאלה ורציתי לבקש את עזרתכם. יש ערימה בת מ איברים. ידוע שפקודת extract-max מבצעת 2logn+1 השוואות בין איברים במקרה הגרוע. צריך לשנות את השגרה כדי שתבצע logn+loglogn+1 השוואות בלבד. ואז גם לשנות אותה כדי שתבצע logn+logloglogn+1 השוואות בלבד... תודה לעוזרים.

 

[shirbi]

זה נשמע מוזר...

איך הגעת לחישוב של מספר ההשוואות באלגוריתם המקורי? הוא נשמע קטן מדי. למה? כי בניית הערימה לוקחת O של n השוואות, ואח"כ אתה טוען שהמיון לוקח 2logn השוואות. כלומר סה"כ, O של מ השוואות, וזה כמובן קטן יותר מהחסם התחתון למיון, שהוא טטה של nlogn. או שאתה לא מדבר על ערימת מקסימום אלא על משהו אחר?

 

[lionsh]

דיברתי על שיגרת extract max

ולא על מיון ערימה עצמו. נתון בתרגיל ששגרה זו מבצעת 2logn + או של 1 השוואות. יש לשנות אותה איכשהו שתבצע את מספר הפעולות הדרושות...