מיון ערימה

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

מיון ערימהאנגלית: 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)