מיון ערימה
מראה
מיון ערימה (באנגלית: Heapsort) הוא אלגוריתם למיון המבוסס על מבנה הנתונים ערימה (Heap). מיון ערימה הוא סוג של מיון בחירה, ובדומה לו מבצע את פעולתו במקום, תוך שימוש בכמות קטנה וקבועה של שטח אחסון. על חומרת מחשב מקובלת, יישום של מיון ערימה הוא איטי במקצת מיישום של מיון מהיר, אך פועל בזמן של גם במקרה הגרוע.
תיאור האלגוריתם
[עריכת קוד מקור | עריכה]![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Heap_sort_example.gif/300px-Heap_sort_example.gif)
בשלב הראשון האלגוריתם בונה ערימה מהמערך (המערך הופך מתכלת לצהוב).
בשלב השני האלגוריתם מוציא את שורש הערימה, מציב במקומו את אחד העלים ומסדר את הערימה מחדש. בכל איטרציה, כל האיברים הירוקים מסודרים מהגדול לקטן מימין לשמאל.
התיאור הבא מתייחס ל"ערימת מקסימום", שבה כל הורה גדול בערכו משני בניו.
- בונים ערימה ממערך של איברים למיון.
- מוציאים מהערימה את השורש (המהווה את הערך המקסימלי), ומכניסים אותו למיקום הפנוי הגדול ביותר במערך. מתקבל מבנה של 'כמעט ערימה' הקטן בגודלו באיבר אחד.
- מוציאים את האיבר האחרון במבנה (ש��יה אחד הערכים הקטנים בערימה) ומציבים אותו במקום השורש שהוצא.
- מבצעים פעולת Heapify שמטרתה לתקן את המבנה ולהפוך אותו שוב לערימה חוקית. מבצעים זאת באמצעות פעולה מחזורית מהשורש ומטה.
- חוזרים שוב על תהליך הוצאת השורש עד אשר הערימה מגיעה לגודל של איבר בודד והמערך מכיל את כל איברי הערימה ממויינים.
פסאודו קוד
[עריכת קוד מקור | עריכה]פונקציות עזר:
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)
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- סימולציה של מיון ערימה בצורה אינטראקטיבית
- מיון ערימה בQueue
- מיון ערימה, באתר MathWorld (באנגלית)
אלגוריתמי מיון | ||
---|---|---|
רקע תאורטי | תורת הסיבוכיות • סימון אסימפטוטי • סדר מלא • רשימה • אלגוריתם תוך-מקומי • מיון יציב | |
אלגוריתמי מיון | אקראי • בועות • בחירה • בסיס • הכנסה • מהיר • מיזוג • מנייה • מסרק • סלים • ערימה • רשת מיון • שייקר • של | |
שונות | מיון טופולוגי • בעיית סידור הפנקייקים של גודמן |