מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/תורי קדימויות/תרגילים/Heapsort/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

גרסה עם Build-Heap[עריכה]

  1. קל לראות שהאלגוריתם עובד: כפי שראינו בבניית ערימה בינרית ממערך, Build-Heap מייצרת ערימה תקינה ממערך, והרי Delete-Min מוציאה ומחזירה את האיבר הקטן ביותר.
  2. הסיבוכיות היא במקרה הגרוע. ראינו מימוש לBuild-Heap שעובד בזמן ,‏ ואנו יודעים שסיבוכיות Delete-Min על ערימה בת איברים היא במקרה הגרוע. סיבוכיות הלולאה 3-4, לכן, היא (ראה גם טורים שימושיים בסדרי גדילה).

גרסה עם סדרת פעולות Insert[עריכה]

  1. אין שינוי בנכונות, כי הלולאה 3-4 גם כן מייצרת ערימה תקינה מהמערך, ואין הבדל מנקודה זו.
  2. אף הסיבוכיות אינה שונה, מפני שבמקום הביטוי (בסעיף הקודם), נקבל כעת . שני הביטויים שקולים (מבחינת סדרי הגדילה).