סיבוכיות זמן ומקום

סיבוכיות זמן:

• המקרה הטוב, הממוצע והגרוע: O(n log n)
  • בניית הערימה היא O(n), וכל אחת מ־n ההוצאות עולה O(log n) עבור ההורדה בערימה. אין מקרה של קלט גרוע שמדרדר את הביצועים.

סיבוכיות מקום:

• O(1)
  • מיון ערימה מסדר מחדש את האיברים בתוך המערך המקורי ודורש רק כמות קבועה של זיכרון נוסף.

סיכום:

• מיון ערימה משלב זמן ריצה מובטח של O(n log n) עם מקום נוסף של O(1) — שילוב שמיון מיזוג ומיון מהיר אינם מציעים יחד.
• הוא אינו יציב (איברים שווים עשויים לשנות את הסדר היחסי שלהם), וזהו החיסרון העיקרי שלו.