מיון בעזרת תור קדימויות (Heap Sort)

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

באנימציה בצד שמאל, ניתן לראות את התהליך של מיון ערמה. תחילה נקבל מערך (בצבע תכלת), ונבנה ממנו את הערמה (בשלב זה המערך הופך לצהוב), על ידי כך שנפעיל את שגרת BUILD-MAX-HEAP, השגרה הזאת מבצעת את MAX-HEAPIFY (שתפקידה להחליק איברים, במורד הערמה, למקומם הנכון לפי תכונות הערמה - עץ בינרי), על חצי מהמערך (מכיוון שזהו גובה הערמה - מתכונות עץ בינרי).

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

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

 

הקוד של האלגוריתם ב פסאודו קוד

(ה ~ נועד לסמן עיגול כלפי מטה)

PARENT (i)
return ~i/2~

LEFT (i)
return 2*i

RIGHT (i)
return 2*i + 1

MAX-HEAPIFY (A, i)
l <- Left(i)
r <- Right (i)
if (l <= heap-size[A] and A[l] > A[I] )
     largest <- l
else largest <- i
if (r <= heap-size[A] and A[r] > A[largest])
     largest <- r
if (largest != r)
     exchange A[I] <-> A[largest]
     MAX-HEAPIFY (A, largest)

BUILD-MAX-HEAP (A)
heap-size[A] <- length[A]
for (i <- ~length[A]/2~ downto 1)
     MAX-HEAPIFY (A, i)

HEAPSORT (A)
BUILD-MAX-HEAP(A)
for (i <- length[A] downto 2) do
     exchange A[1] <-> A[i]
     heap-size[A] <- heap-size[A] -1
     MAX-HEAPIFY (A, 1)

 

הסבר מופשט:

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

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים:

משהו..

 

סיבוכיות זמן ריצה: ((O(n*lg(n.

שימו לב למרות שבמקרה הגרוע מיון זה מתבצע באותה מהירות כמו הזמן הממוצע של Quick Sort, המשתנים הקבועים שלו גדולים ולכן, לרוב, זמן הריצה במקרה הגרוע של Heap Sort יהיה גדול יותר מזמן הריצה ממוצע של Quick Sort (אך רק בקבועים ולא בסדר גודל).

סיבוכיות מקום: (O(n.