streamalism.org

1. הקדמה

במדריך זה נראה כיצד עובד Heap Sort וניישם אותו ב- Java.

מיון הערימה מבוסס על מבנה הנתונים של הערימה. על מנת להבין את Heap Sort כראוי, נעבור תחילה ב- Heaps ובאופן יישומם.

2. מבנה נתונים של ערימה

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

כמו כן, לצמתים יכולים להיות ילדים. אם לצומת אין ילדים, אנו קוראים לו עלה.

מה ש Heap מייחד הם שני דברים:

1. הערך של כל צומת חייב להיות פחות או שווה לכל הערכים המאוחסנים בילדיו
2. זה עץ שלם, כלומר יש לו את הגובה הכי פחות אפשרי

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

האופן בו אנו אוכפים כללים אלה תלוי ביישום.

בדרך כלל משתמשים בערימות ליישום תורי עדיפות מכיוון ש- Heap הוא יישום יעיל מאוד של חילוץ האלמנט הפחות (או הגדול ביותר).

2.1. גרסאות ערימה

ל- Heap גרסאות רבות, כולן שונות בפרטי יישום מסוימים.

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

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

הדרך הקלה ביותר לאכוף את הכלל השני היא שימוש בעץ בינארי מלא. עץ בינארי מלא עוקב אחר כמה כללים פשוטים:

1. אם לצומת יש רק ילד אחד, זה צריך להיות הילד השמאלי שלו
2. רק בצומת הימני ביותר ברמה העמוקה ביותר יכול להיות ילד אחד בדיוק
3. עלים יכולים להיות רק ברמה העמוקה ביותר

בואו נראה את הכללים האלה עם כמה דוגמאות:

 1 2 3 4 5 6 7 8 9 10 () () () () () () () () () () / \ / \ / \ / \ / \ / / / \ () () () () () () () () () () () () () () / \ / \ / \ / / \ () () () () () () () () () / ()

העצים 1, 2, 4, 5 ו -7 פועלים לפי הכללים.

עץ 3 ו -6 מפרים את הכלל הראשון, 8 ו -9 את הכלל השני, ו -10 מפרים את הכלל השלישי.

במדריך זה, נתמקד במיני-ערימה עם עץ בינארי יישום.

2.2. הכנסת אלמנטים

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

אנו יכולים להוסיף אלמנט בשלבים הבאים:

1. צור עלה חדש שהוא החריץ הזמין ביותר ברמה העמוקה ביותר ואחסן את הפריט בצומת זה
2. אם האלמנט פחות מההורה, אנו מחליפים אותם
3. המשך בשלב 2, עד שהאלמנט קטן מההורה או שהוא יהפוך לשורש החדש

שים לב, שלב 2 לא יפר את הכלל Heap, מכיוון שאם נחליף את ערך הצומת בפחות, הוא עדיין יהיה פחות ממה שהוא ילדים.

בואו נראה דוגמא! אנו רוצים להכניס 4 לערימה זו:

 2 / \ / \ 3 6 / \ 5 7

הצעד הראשון הוא ליצור עלה חדש המאחסן 4:

 2 / \ / \ 3 6 / \ / 5 7 4

מכיוון ש -4 פחות מההורה, 6, אנו מחליפים אותם:

 2 / \ / \ 3 4 / \ / 5 7 6

עכשיו אנחנו בודקים אם 4 פחות מההורה או לא. מכיוון שההורה שלו הוא בן 2, אנחנו עוצרים. הערימה עדיין בתוקף, והכנסנו את מספר 4.

בוא נכניס 1:

 2 / \ / \ 3 4 / \ / \ 5 7 6 1

עלינו להחליף 1 ו -4:

 2 / \ / \ 3 1 / \ / \ 5 7 6 4

כעת עלינו להחליף 1 ו -2:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

מכיוון ש- 1 הוא השורש החדש, אנו עוצרים.

3. יישום ערימה בג'אווה

מכיוון שאנו משתמשים ב- עץ בינארי מלא, אנו יכולים ליישם אותו באמצעות מערך: אלמנט במערך יהיה צומת בעץ. אנו מסמנים כל צומת במדדי המערך משמאל לימין, מלמעלה למטה בדרך הבאה:

 0 / \ / \ 1 2 / \ / 3 4 5

הדבר היחיד שאנחנו צריכים זה לעקוב אחר כמה אלמנטים שאנחנו מאחסנים בעץ. בדרך זו האינדקס של האלמנט הבא שנרצה להכניס יהיה בגודל המערך.

באמצעות אינדקס זה אנו יכולים לחשב את האינדקס של צמתי ההורה והילד:

• הוֹרֶה: (אינדקס - 1) / 2
• ילד שמאל: 2 * אינדקס + 1
• ילד נכון 2 * אינדקס + 2

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

יישום בסיסי של עץ בינארי נראה כך:

class BinaryTree {רשימה אלמנטים = ArrayList חדש (); ריק להוסיף (E e) {elements.add (e); } בוליאני isEmpty () {return elements.isEmpty (); } E elementAt (int index) {return elements.get (index); } int parentIndex (int index) {return (index - 1) / 2; } int leftChildIndex (int index) {return 2 * index + 1; } int rightChildIndex (int index) {return 2 * index + 2; }}

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

ערימה בכיתה {// ... ריק להוסיף (E e) {elements.add (e); int elementIndex = elements.size () - 1; בעוד (! isRoot (elementIndex) &&! isCorrectChild (elementIndex)) {int parentIndex = parentIndex (elementIndex); החלפה (elementIndex, parentIndex); elementIndex = parentIndex; }} isRoot בוליאני (אינדקס int) {אינדקס החזרה == 0; } בוליאני isCorrectChild (אינדקס int) {return isCorrect (parentIndex (index), index); } בוליאני isCorrect (int parentIndex, int childIndex) {if (! isValidIndex (parentIndex) ||! isValidIndex (childIndex)) {return true; } return elementAt (parentIndex) .compareTo (elementAt (childIndex)) <0; } isValidIndex בוליאני (אינדקס int) {אינדקס החזרה <elements.size (); } החלפת חלל (int index1, int index2) {E element1 = elementAt (index1); אלמנט E = אלמנט At (אינדקס 2); elements.set (index1, element2); elements.set (index2, element1); } // ...}

שים לב, מכיוון שאנחנו צריכים להשוות את האלמנטים, הם צריכים ליישם java.util.Comparable.

4. ערימת מיון

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

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

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

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

אנו ממשיכים להחליף עד שהאלמנט הופך לעלה, או שהוא פחות מכל ילדיו.

בואו נמחק את השורש מעץ זה:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

ראשית, אנו מניחים את העלה האחרון בשורש:

 4 / \ / \ 3 2 / \ / 5 7 6

ואז, מכיוון שהוא גדול משני ילדיו, אנו מחליפים אותו עם הילד הכי פחות שלו, שהוא 2:

 2 / \ / \ 3 4 / \ / 5 7 6

4 הוא פחות מ 6, אז אנחנו עוצרים.

5. יישום מיון ערימה בג'אווה

עם כל מה שיש לנו, הסרת השורש (popping) נראית כך:

ערימה בכיתה {// ... E pop () {if (isEmpty ()) {throw new IllegalStateException ("אתה לא יכול לקפוץ מערימה ריקה"); } תוצאה E = elementAt (0); int lasElementIndex = elements.size () - 1; החלפה (0, lasElementIndex); elements.remove (lasElementIndex); int elementIndex = 0; בעוד (! isLeaf (elementIndex) &&! isCorrectParent (elementIndex)) {int smallerChildIndex = smallerChildIndex (elementIndex); החלפה (elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } להחזיר תוצאה; } בוליאני isLeaf (אינדקס int) {return! isValidIndex (leftChildIndex (index)); } בוליאני isCorrectParent (אינדקס int) {return isCorrect (אינדקס, leftChildIndex (אינדקס)) && isCorrect (אינדקס, rightChildIndex (אינדקס)); } int smallerChildIndex (int index) {int leftChildIndex = leftChildIndex (index); int rightChildIndex = rightChildIndex (אינדקס); אם (! isValidIndex (rightChildIndex)) {להחזיר leftChildIndex; } אם (elementAt (leftChildIndex) .compareTo (elementAt (rightChildIndex)) <0) {return leftChildIndex; } להחזיר rightChildIndex; } // ...}

כמו שאמרנו קודם, מיון הוא פשוט יצירת ערימה והסרת השורש שוב ושוב:

ערימה בכיתה {// ... סטטי  מיון רשימות (אלמנטים ניתנים לשינוי) {ערימת ערמה = של (אלמנטים); תוצאת רשימה = ArrayList חדש (); בעוד (! heap.isEmpty ()) {result.add (heap.pop ()); } להחזיר תוצאה; } סטטי  ערימה של (אלמנטים ניתנים לניתנים) {תוצאה של ערימה = ערימה חדשה (); עבור (אלמנט E: אלמנטים) {result.add (אלמנט); } להחזיר תוצאה; } // ...}

אנו יכולים לוודא שהוא עובד עם הבדיקה הבאה:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList () {// נתון אלמנטים ברשימה = Arrays.asList (3, 5, 1, 4, 2); // כאשר List sortedElements = Heap.sort (אלמנטים); // ואז טוענים כי (sortedElements) .isEqualTo (Arrays.asList (1, 2, 3, 4, 5)); }

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

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

מיון ערימה מורכב מ שני שלבים מרכזיים, מכניסה אלמנט ו הסרה צומת השורש. לשני השלבים המורכבות O (יומן n).

מכיוון שאנחנו חוזרים על שני השלבים n פעמים, מורכבות המיון הכוללת היא O (n יומן n).

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

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

שים לב, כי בנתונים מהעולם האמיתי, Quicksort בדרך כלל מבצע יותר מ- Heap Sort. רירית הכסף היא ש- Heap Sort תמיד יש את המקרה הגרוע ביותר O (n יומן n) מורכבות זמן.

7. מסקנה

במדריך זה ראינו יישום של ערימה בינארית ומיון ערימה.

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

כרגיל, הדוגמאות זמינות ב- GitHub.