מיון ערימה

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

[עריכה] תיאור האלגוריתם

התיאור הבא מתייחס ל"ערימת מקסימום", שבה כל הורה גדול בערכו משני בניו.

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

[עריכה] פסאודו קוד

פונקציות עזר:

 Build-Heap(A)
 heap_size[A] <- length[A]
 for i <- length[A]/2 Downto 1
   do Heapify(A,i)

 Heapify(A,i)
 l <- LEFT(i)     //the left son of vertex i     // i הבן השמאלי של צומת
 r <- RIGHT(i)    //the right son of vertex i    // i הבן הימני של צומת
 if l <= heapsize[A] and A[l] > A[i]
   then largest <- l
   else largest <- i
 if r<=heapsize[A] and A[r] > A[largest]
   then largest <- r
 if largest != i
   then exchange A[i] <-> A[largest]
 Heapify(a,largest)

 HeapSort(A)
 Build-Heap(A)
 for i <- length[A] downto 2
   do exchange A[1] <-> A[i]
     heap-size[A] <- heap-size[A]-1
     Heapify(A,i)