מיון ערימה

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

תיאור האלגוריתם

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

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

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)            // i הבן השמאלי של צומת
r <- RIGHT(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,1)