Max Heap ב-Java

העץ הבינארי

ב-Java, ישנם סוגים רבים ושונים של מבני נתונים. הערימה מבוססת על מבנה עץ הנקרא עץ בינארי . עץ בינארי מורכב מצמתים, שלכל אחד מהם יכולים להיות לכל היותר 2 צמתים צאצאים: עץ בינארי מורכב מצמת אב שיכול להיות מ-0 עד 2 צמתים. יכול להיות לו צומת בן שמאל ו/או צומת ילד ימני, או ללא צמתים כלל. בעץ בינארי שלם, כל הצמתים מלאים למעט הרמה האחרונה שיכולה להיות מלאה, אבל לא חייבת להיות מלאה. הרמה האחרונה, הרמה ה-n, יכולה להיות מ-1 עד 2n צמתים, כאשר הראשון נמצא ב-n = 0 והוא השורש.

מקס ערימה

Max heap (או maxheap) הוא עץ בינארי שלם . הדבר החשוב בו הוא שלצומת האב חייב להיות ערך גדול או שווה לזה של הצמתים הימניים והילדים. אם לא מקפידים על זה, אין לך ערימה מקסימלית. Min heap, לעומת זאת, הוא ההפך כאשר השורש הוא הערך הקטן ביותר עם צמתים עוקבים שגדלים בערכם; לכל צומת צאצא יש ערך גדול או שווה להורה שלו. זה גם עץ בינארי שלם. דוגמה לערימה מקסימלית היא: ערימה מקסימלית יכולה להיבנות ממערך. מערך זה ייחשב במונחים של עץ. עבור ערימה, אם השורש, (צומת האב העליון של העץ) מאוחסן במיקום (אינדקס) n, הוא מוגדר עבור מערך, theArray , בתור theArray[n] . הצמתים הימניים והילדים הימניים נמצאים, לפיכך, ב- theArray[2n+1] וב- theArray[2n+2] בהתאמה. עבור הערימה המקסימלית, השורש נמצא ב- theArray[0] . עבור הרמה n, שורש n = 0: theArr[n] הוא צומת האב theArr[(2*n)+1] הוא צומת הילד השמאלי theArr[(2*n)+2] הוא צומת הילד הימני

כיתת PriorityQueue

ניתן ליישם ערימות ב-Java באמצעות מחלקת PriorityQueue . PriorityQueue משמשים למציאת הפריט החשוב ביותר או הפחות חשוב באוסף. ניתן למצוא את המחלקה PriorityQueue ב- java.util.package . PriorityQuees חייבים להיווצר מאובייקטים ברי השוואה כך שהם ממוקמים בסדר מסוים בתור. ל-PriorityQueue יכול להיות השוואת כך שתבוצע השוואה בין האובייקטים לבין התור שנוצר על פי השוואה זו. דוגמה היא:

import java.util.Comparator;
import java.util.PriorityQueue;

public class Main
{
    public static void main(String[] args) {
        // Create PriorityQueue with comparator for ascending order of array length
        PriorityQueue intQueue = new PriorityQueue((a,b) -> a - b);
        Integer [] array1 = {1, 2, 4, 6, 8, 9};
        Integer [] array2 = {3, 6, 9};
        Integer [] array3 = {2, 4, 8, 16, 32, 64, 128};
        Integer [] array4 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55};
        Integer [] array5 = {4};

        //Add the array lengths to intQueue
        intQueue.add(array1.length);
        intQueue.add(array2.length);
        intQueue.add(array3.length);
        intQueue.add(array4.length);
        intQueue.add(array5.length);
        //Write out contents of intQueue as stored
        while (intQueue.size() != 0) {
            System.out.println(intQueue.remove());
        }
    }
}

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

יישום של PriorityQueue ליצירת ערימה מקסימלית

מחלקת PriorityQueue כברירת מחדל היא ערימה מינימלית ללא השוואה. ערימה מינימלית היא ההיפך מערימה מקסימלית ולכן השורש הוא הערך הקטן ביותר וצמתי צאצא עוקבים גדולים או שווים לשורש ולצמתים ההורים הבאים. מסיבה זו, עבור max heap, יש צורך להשתמש ב-reverseOrder() ממסגרת Collections של Java בתור ההשוואה. זה יבטיח שנקבל ערימה מקסימלית ולא ערימה מינימלית. למחלקה זו יש שיטות שימושיות כגון add() , contains() , remove() , poll() ו- peek() . אלמנטים מתווספים לתור ויכולים להיות בכל סדר. תור ה-PriorityQueue החדש יאחסן את האלמנטים האלה כ-heap מקסימום בסדר הפוך. כאשר התור ייכתב החוצה, הסדר יהיה: שורש שמאל-ילד עם שורש כהורה (Left-child_1) ילד ימני עם שורש כהורה (Right-child_1) Left-child עם Left-child_1 כהורה (Left-child_2 ) ילד ימני עם ילד-שמאל_1 כהורה (ילד-ימני_2) ילד-שמאלי עם ילד-ימני_1 כהורה (ילד-שמאל_3) ילד ימני עם ילד-ימין_1 כהורה (ילד-ימני_3) ילד-שמאל עם ילד-שמאל_2 כהורה (Left-child_4) Right-child עם Left-child_2 כהורה (Right-child_4), וכו' הקוד הבא הוא דוגמה לאופן שבו נוצרת ערימה מקסימלית (maxheap) ב-java. הדבר הראשון שצריך לעשות הוא למלא מערך בערכים שעבורם תיווצר הערימה המקסימלית. זה נקרא theArray . לאחר מכן, נוצר PriorityQueue , theQueue , ולאחר מכן מוסיפים לזה את האלמנטים מה- theArray . זה משתמש בשיטה add() , למשל theQueue.add(10) כדי להוסיף 10 לסוף התור. כדי להמחיש חלק מהפונקציונליות של PriorityQueue Class, השיטה peek() משמשת לאחר מכן כדי למצוא את ראש הערימה, וזהו הערך המקסימלי, במקרה זה, 99. המשימה הבאה היא לבדוק את גודל הערימה באמצעות size() שנמצא כ-9 וזה מודפס למסוף. שיטה writeMaxHeap כותבת את האלמנטים בתור לפי סדר השורש, ילד שמאלי עם שורש כהורה, ילד ימני עם שורש כהורה, ילד שמאלי עם ילד שמאלי ראשון כהורה, ילד ימני עם ילד שמאלי ראשון בתור הורה, ילד ימני עם הילד הימני הראשון כהורה, הילד השמאלי עם הילד הימני הראשון כהורה וכו', כאשר הערכים הבאים משתמשים בילדים משמאל וימין כהורים באותו הסדר כמו לעיל. שיטת PriorityQueue contains(J) משמשת כדי לגלות אם אלמנט ספציפי, J , נמצא בתור. במקרה זה אנו מחפשים J = 10. בדוגמה שלנו, זה נכון שזה בתור אז זה נכתב לקונסולה כאמת. שיטה נוספת של PriorityQueue , remove(J) משמשת לאחר מכן להסרת J = 10 מהתור . כדי להמחיש יותר את הפונקציונליות של PriorityQueue , השיטה poll() משמשת להסרת אלמנט head (ערך מקסימלי) באמצעות לולאת while , בכל פעם מסירים את אלמנט ה-head בתור החדש ומקטינים את גודל התור באחד בכל פעם. זה קורה בשיטה writeQueue שנקראת מ-main. בכל פעם שהרכיב שהוסר מודפס לקונסולה. לתור המקורי לא יישארו אלמנטים בסופו של דבר. האלמנטים המודפסים הם הערימה המקסימלית בסדר יורד של הערך, כאשר ראש התור מודפס בכל פעם.

mport java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeap {

       public static void writeQueue(PriorityQueue<Integer> priorityQueue)
       {
           // Write out elements in queue, priorityQueue, and remove them using poll()
           while(priorityQueue.size() != 0)
           {
               System.out.println(priorityQueue.poll());
           }
       }

       public static void writeMaxHeap(PriorityQueue<Integer> priorityQueue)
       {
           // Write out elements in queue as a max heap - root, left child, right child, etc
           for (Integer element : priorityQueue) {
               System.out.println(element);
           }
       }

       public static void main(String args[])
       {
           // Array of numbers to create a max heap array from
           int[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};

           // theQueue is created
           PriorityQueue<Integer> theQueue =
                   new PriorityQueue<Integer>(Collections.reverseOrder());

           // Elements are added to theQueue
           for (int i = 0 ; i <theArray.length; ++i)
           {
               theQueue.add(theArray[i]);
           }

           // The head or root element (priority element) is printed out
           System.out.println("The root value is : " +  theQueue.peek());

           // Find size of theQueue. Use method size()
           Integer s = theQueue.size();
           System.out.println("Size of theQueue? " + s);

           // All elements of theQueue are printed in terms of parent,
           // left child, right child
           System.out.println("theQueue written using for loop:");
           writeMaxHeap(theQueue);

           // Does theQueue contain 10? Use method contains()
           boolean b = theQueue.contains(10);
           System.out.println("Does theQueue contain 10? " + b);

           // Erasing value 10 from array using remove()
           theQueue.remove(10);

           // All elements of theQueue are printed out and removed.
           // Each one is the maximum value left in the queue.
           // At the end theQueue will be empty
           System.out.println("theQueue written out using poll():");
           writeQueue(theQueue);

           // Find size of theQueue. Use method size()
           s = theQueue.size();
           System.out.println("Size of theQueue? " + s);
       }
   }

תְפוּקָה:

Max Heapify

האלגוריתם Max Heapify משמש כדי להבטיח שעץ בינארי הוא ערימה מקסימלית. אם אנחנו נמצאים בצומת, n, והצמתים הילדיים שלו, שמאל וימין הם גם ערימות מקסימום בעצמם, אז מצוין, יש לנו ערימה מקסימלית. אם זה לא כך בכל העץ אז אין לנו ערימה מקסימלית. האלגוריתם Max Heapify משמש למיון העץ כך שיעמוד בעקרונות maxheap. Max Heapify עובד על צומת אחד בלבד. אם הדרישה היא שהמערך הוא מערך ערימה מקסימלית, יש להמיר את כל עצי המשנה ל-maxheap לפני השורש, אחד בכל פעם. יש להשתמש באלגוריתם בכל צומת. זה ייעשה בצמתים N/2 (העלים יעמדו בדרישות הערימה המקסימלית). מורכבות הזמן של הערימה היא O(NlogN), ועבור צומת אחד בגובה X, מורכבות הזמן היא O(X). הקוד הבא מראה כיצד maxheapify עץ (מערך).

public class MaxHeapify

{
   public static Integer[] maxHeapify(Integer[ ] array, Integer i)
   {
       // Create left-child and right-child for the node in question
       Integer leftChild = 2 * i + 1;
       Integer rightChild = 2 * i + 2;

       // Assign maxVal to parent node, i
       Integer maxVal = i;

       // Set maxVal to greater of the two: node or left-child
       if( leftChild < array.length && array[leftChild] > array[maxVal] )
           maxVal = leftChild;

       // Set maxVal to greater of the two: maxVal or right-child
       if( rightChild < array.length && array[rightChild] > array[maxVal] )
           maxVal = rightChild;

       // Check if maxVal is not equal to parent node, then set parent node to
       // maxVal, swap values and then do a maxheapify on maxVal
       // which is now the previous parent node
       if( maxVal != i )
       {
           Integer value = array[i];
           array[i] = array[maxVal];
           array[maxVal] = value;
           array = maxHeapify(array, maxVal);
       }

       return array;
   }


   public static Integer[] maxHeapCreate(Integer array[])
   {
       // Call maxHeapify to arrange array in a max heap
       Integer [] theNewArr = array;
       for( Integer i = array.length/2; i >= 0; i-- )
           theNewArr = maxHeapify(array, i);

       return theNewArr;
   }

   public static void main(String[] args)
   {
       // Create array to be maxheapified, theArray,
       // and array, newArray, to write results into, by calling maxheapCreate
       // newArray will now be a maxheap
       Integer[] theArray = {5, 3, 13, 10, 99, 19, 6, 51, 9};
       Integer[ ] newArray = maxHeapCreate(theArray);

       // Print out contents of newArray
       System.out.println("newArray:");
       for(int i = 0; i < newArray.length; ++i)
       {
           System.out.println(newArray[i]);
       }

       // Print out labelled contents of newArray
       System.out.println(" root : " + newArray[0]);
       for (int i = 0; i <= newArray.length/2 - 1; i++) {
           System.out.print(" parent node : " + newArray[i] + " left child : " +
                            newArray[(2*i)+1] + " right child :" + newArray[(2*i)+2]);
           System.out.println();
       }
  }
}

מתן פלט: בקוד זה, המערך נוצר ומתמלא במספרים. נוצר מערך שני, newArray והפעם הוא יכיל את התוצאה של השיטה, maxheapCreate , מערך ה-max heap. השיטה maxHeapCreate נקראת מ- main , וכאן נוצר מערך חדש, theNewArr , ומתמלא בתוצאות maxHeapify . זה נעשה על ידי לולאה של מעל מחצית מגודל מערך הקלט. עבור כל מעבר של הלולאה, שיטה maxHeapify נקראת מתחילה באלמנט באמצע המערך וכלה בראשון. עבור כל קריאה של maxHeapify מוצאים את הילד השמאלי והילד הימני של צומת האב, i, ונעשות בדיקות כדי למצוא מי הוא הגדול מבין השלושה, ומגדיר את זה כ- maxVal . אם maxVal אינו שווה לצומת האב אז מתבצעת החלפה כך שצומת האב ו- maxVal יוחלפו ואז maxHeapify נקרא שוב הפעם ב- maxVal ואותם השלבים מבוצעים כמו קודם. בסופו של דבר תיווצר הערימה המקסימלית ולא יהיו עוד איטרציות לביצוע. המערך המעודכן, array , מוחזר כעת ל- main בתור newArray ולאחר מכן כל רכיב עוקב מודפס למסוף. newArray הוא כעת ערימה מקסימלית. שימו לב, שכמו בדוגמה הקודמת באמצעות PriorityQueue, המספרים נכתבים: שורש, ילד ימני של השורש כהורה, ילד שמאלי של השורש כהורה, בן ימני של הילד הימני הראשון כהורה, ילד שמאלי של השורש הראשון. ילד שמאלי כהורה, ילד ימני של הילד השמאלי הראשון כהורה, ילד שמאלי של הילד הימני הראשון כהורה וכו'. הם בסדר מעט שונה מאלה בעת שימוש ב- PriorityQueue מכיוון שההשוואה נעשית בין אלמנטים עוקבים ואילו בדוגמה של maxheapify, הצומת מושווה לשני האלמנטים העוקבים הבאים במערך ומוחלף עבור הערך הגדול ביותר. בקיצור, משתמשים בשני אלגוריתמים שונים. שניהם יוצרים ערימה מקסימלית.

סיכום

אז כאן בדקנו את ה-max heap וכיצד ניתן ליצור אותו עם PriorityQueue או עם אלגוריתם Max Heapify. שימוש ב- PriorityQueue עם reverseOrder() הוא דרך מסודרת לעשות זאת ובשיטה המומלצת. עם זאת, אתה יכול ללמוד דוגמאות אלה ולכתוב שיטות משלך מכיוון שזה יהיה תרגיל קידוד טוב שיעזור לך להצליח בראיון שלך עבור Java Junior.