במאמר זה, נדון באלגוריתם Heapsort. מיון ערימה מעבד את האלמנטים על ידי יצירת ערימת המינימום או הערימה המקסימלית באמצעות האלמנטים של המערך הנתון. Min-heap או max-heap מייצגים את סדר המערך שבו אלמנט השורש מייצג את האלמנט המינימלי או המקסימלי של המערך.

מיון ערימה בעצם מבצע באופן רקורסיבי שתי פעולות עיקריות -

• בנה ערימה H, תוך שימוש באלמנטים של מערך.
• מחק שוב ושוב את אלמנט השורש של הערימה שנוצרה ב-1^רחובשלב.

לפני שנדע יותר על מיון הערימה, בואו נראה תחילה תיאור קצר של ערימה.

מה זה ערימה?

ערמה היא עץ בינארי שלם, והעץ הבינארי הוא עץ שבו לצומת יכולים להיות שני ילדים לכל היותר. עץ בינארי שלם הוא עץ בינארי שבו כל הרמות מלבד הרמה האחרונה, כלומר צומת עלים, צריכות להיות מלאות לחלוטין, וכל הצמתים צריכים להיות מוצדקים שמאלה.

מהו מיון ערימה?

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

Heapsort הוא אלגוריתם המיון במקום.

אופס

עכשיו, בואו נראה את האלגוריתם של מיון ערימה.

אַלגוֹרִיתְם

 HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End 

BuildMaxHeap(arr)

 BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End 

MaxHeapify(arr,i)

 MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End 

עבודה של אלגוריתם מיון ערימה

כעת, בואו נראה את פעולתו של אלגוריתם Heapsort.

במיון ערימה, בעצם, ישנם שני שלבים המעורבים במיון האלמנטים. על ידי שימוש באלגוריתם מיון הערמות, הם כדלקמן -

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

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

ראשית, עלינו לבנות ערימה מהמערך הנתון ולהמיר אותה לערמה מקסימלית.

לאחר המרת הערימה הנתונה לערימה מקסימלית, רכיבי המערך הם -

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

לאחר החלפת אלמנט המערך 89 עם אחד עשר, והמרת הערימה ל-max-heap, האלמנטים של המערך הם -

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

לאחר החלפת אלמנט המערך 81 עם 54 והמרת הערימה ל-max-heap, האלמנטים של המערך הם -

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

מחרוזת ב-int

לאחר החלפת אלמנט המערך 76 עם 9 והמרת הערימה ל-max-heap, האלמנטים של המערך הם -

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

לאחר החלפת אלמנט המערך 54 עם 14 והמרת הערימה ל-max-heap, האלמנטים של המערך הם -

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

לאחר החלפת אלמנט המערך 22 עם אחד עשר והמרת הערימה ל-max-heap, האלמנטים של המערך הם -

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

לאחר החלפת אלמנט המערך 14 עם 9 והמרת הערימה ל-max-heap, האלמנטים של המערך הם -

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

לאחר החלפת אלמנט המערך אחד עשר עם 9, האלמנטים של המערך הם -

כעת, לערמה נותר רק אלמנט אחד. לאחר מחיקתו, הערימה תהיה ריקה.

לאחר השלמת המיון, רכיבי המערך הם -

כעת, המערך ממוין לחלוטין.

מורכבות מיון ערימה

כעת, בואו נראה את מורכבות הזמן של מיון ערימה במקרה הטוב, במקרה הממוצע והמקרה הגרוע ביותר. נראה גם את מורכבות החלל של Heapsort.

1. מורכבות זמן

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

מורכבות הזמן של מיון ערימה היא O(n log) בכל שלושת המקרים (המקרה הטוב ביותר, המקרה הממוצע והמקרה הגרוע ביותר). הגובה של עץ בינארי שלם בעל n אלמנטים הוא לְהַרְגִיעַ.

2. מורכבות החלל

• מורכבות החלל של מיון ערימה היא O(1).

יישום של Heapsort

כעת, בואו נראה את התוכניות של Heap ממוינות בשפות תכנות שונות.

תכנית: כתוב תוכנית ליישם מיון ערמות בשפת C.

 #include /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>