7.2 מיון-ערמה

מבנה נתונים ואלגוריתמים

ציינו קודם לכן, כאשר דנו בערמה, כי בדומה לשימוש שנעשה בה בתור קדימויות היא גם משמשת כאמצעי מיון, כאשר הביצוע נעשה באופן הבא:

1. בניית ערמה.

2. הוספת כל פריט לערמה (תוך שמירה על תכונות הערימה).

3. לאחר שכל הפריטים הוספו, הסרתם נעשית אחד אחרי השני (תוך השבת תכונות הערימה לאחר כל הסרה).

הסרה והוספה הן פעולות O(logn). יש צורך לבצע n הוספות והסרות ומתקבל אלגוריתם

של O(nlogn). אנו נבחן אלגוריתם יעיל נוסף למיון הנקרא מיון-מהיר (quick sort), ולאחר מכן נשווה בינו לבין מיון ערמה.

אנימציה

האנימציה הבאה עושה שימוש בשינוי קל של הגישה שהוזכרה לעיל לגבי מיון. ניתן להבחין כי היא ממקמת תחילה את כל הפריטים בתוך המערך, ורק אז לוקחת פריטים מתחתית הערמה ומשיבה את תכונות הערימה, זאת במקום להשיב את תכונות הערימה לאחר כל הכנסת פריט כפי שמוצע באלגוריתם שהוזכר כאן.

שים לב כי האנימציה מראה שהמידע:

· מאוחסן במערך (כמו ביישום של האלגוריתם)

· וכן בצורה של עץ - כך שמבנה הערמה ניתן בבירור להבחנה.

המשך ל: מיון-מהיר חזור ל: תוכן עניינים