Max Heap sa Java

Ang Binary Tree

Sa Java, mayroong maraming iba't ibang uri ng mga istruktura ng data. Ang bunton ay batay sa isang istraktura ng puno na tinatawag na isang binary tree . Binubuo ang isang binary tree ng mga node, na ang bawat isa ay maaaring magkaroon ng maximum na 2 child node: Ang isang binary tree ay binubuo ng isang parent node na maaaring magkaroon ng 0 hanggang 2 node. Maaari itong magkaroon ng left-child node at/o right-child node, o walang node. Sa isang kumpletong binary tree, ang lahat ng mga node ay pinupunan maliban sa huling antas na maaaring puno, ngunit hindi kailangang puno. Ang huling antas, ang ika-na antas, ay maaaring magkaroon ng mula 1 hanggang 2n node, kung saan ang una ay nasa n = 0 at ang ugat.

Max Heap

Ang max heap (o maxheap) ay isang kumpletong binary tree . Ang mahalagang bagay tungkol dito ay DAPAT may halaga ang parent node na mas malaki kaysa o katumbas ng value ng left- and right-child node. Kung hindi ito susundin, wala kang max heap. Ang Min heap, sa kabilang banda, ay ang kabaligtaran ng ugat bilang ang pinakamaliit na halaga na may sunud-sunod na mga node na tumataas ang halaga; bawat child node ay may halagang mas malaki kaysa o katumbas ng magulang nito. Ito rin ay isang kumpletong binary tree. Ang isang halimbawa ng isang max heap ay: Ang max heap ay maaaring itayo mula sa isang array. Ang array na ito ay iisipin sa mga tuntunin ng isang puno. Para sa isang heap, kung ang ugat, (top parent node ng puno) ay naka-imbak sa posisyon (index) n, ito ay tinukoy para sa array, theArray , bilang theArray[n]. Ang left- at right-child node ay, samakatuwid, ay nasa theArray[2n+1] at theArray[2n+2] ayon sa pagkakabanggit. Para sa max heap, ang ugat ay nasa theArray[0] . Para sa antas n, ugat n = 0: angArr[n] ay ang parent node angArr[(2*n)+1] ay ang kaliwang child node angArr[(2*n)+2] ay ang kanang child node

Ang PriorityQueue Class

Maaaring ipatupad ang Heaps sa Java gamit ang PriorityQueue Class. Ginagamit ang PriorityQueues upang mahanap ang pinakamahalaga o hindi gaanong mahalagang item sa isang koleksyon. Ang klase ng PriorityQueue ay matatagpuan sa java.util.package . Ang PriorityQueues ay dapat mabuo ng mga bagay na maihahambing upang mailagay ang mga ito sa isang partikular na pagkakasunud-sunod sa pila. Ang PriorityQueue ay maaaring magkaroon ng isang comparator upang ang isang paghahambing sa pagitan ng mga bagay ay ginawa at ang queue ay nabuo ayon sa paghahambing na ito. Ang isang halimbawa ay:

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());
        }
    }          
}

Nagbibigay ng output: Sa halimbawang ito, ang default na laki ng intQueue ay 11, kaya't hindi nakasaad (karaniwan ay ang unang argumento bago ang comparator) at ang comparator ay ibinigay bilang: Gagawa ito ng paghahambing sa pagitan ng mga item sa intQueue at pag-uri-uriin ito sa mga haba ng array ng pataas na pagkakasunud-sunod.

Pagpapatupad ng PriorityQueue para Gumawa ng Max Heap

Nagde-default ang PriorityQueue Class sa min heap nang walang comparator. Ang min heap ay ang kabaligtaran ng max heap at kaya ang root ay ang pinakamaliit na value at ang sunud-sunod na child node ay mas malaki o katumbas ng root at kasunod na parental node. Para sa kadahilanang ito, para sa max heap, kinakailangang gumamit ng reverseOrder() mula sa balangkas ng Collections ng Java bilang comparator. Titiyakin nito na makakakuha tayo ng max heap at hindi isang min heap. Ang Klase na ito ay may mga kapaki-pakinabang na pamamaraan gaya ng add() , contains() , remove() , poll() , at peek() . Ang mga elemento ay idinaragdag sa queue at maaaring nasa anumang pagkakasunud-sunod. Ang bagong PriorityQueue queue ay mag-iimbak ng mga elementong iyon bilang isang max heap sa reverse order. Kapag naisulat na ang pila, ang pagkakasunud-sunod ay: Root Kaliwa-anak na may ugat bilang magulang (Kaliwa-anak_1) Kanan-anak na may ugat bilang magulang (Kanan-anak_1) Kaliwang-anak na may Kaliwang-anak_1 bilang magulang (Kaliwa-anak_2 ) Kanang-bata na may Kaliwa-anak_1 bilang magulang (Kanang-anak_2) Kaliwa-anak na may Kanan-anak_1 bilang magulang (Kaliwa-anak_3) Kanang-anak na may Kanan-anak_1 bilang magulang (Kanang-anak_3) Kaliwa-anak na may Kaliwa-anak_2 bilang magulang (Kaliwa-anak_4) Kanang-anak na may Kaliwang-anak_2 bilang magulang (Kanang-anak_4), atbpAng sumusunod na code ay isang halimbawa kung paano nilikha ang isang max heap (maxheap) sa java. Ang unang bagay na dapat gawin ay punan ang isang array ng mga halaga kung saan malilikha ang max heap. Ito ay tinatawag na theArray . Susunod, isang PriorityQueue , theQueue , ay nilikha at pagkatapos ay ang mga elemento mula sa theArray ay idinagdag dito. Gumagamit ito ng paraan add() , hal. theQueue.add(10) upang magdagdag ng 10 sa dulo ng queue. Upang ilarawan ang ilan sa mga functionality ng PriorityQueue Class, ginamit ang method peek() para mahanap ang head ng heap, at ito ang pinakamataas na value, sa kasong ito, 99. Ang susunod na gawain ay suriin ang laki ng heap gamit ang size()na natagpuang 9 at ito ay naka-print sa console. Isinulat ng method writeMaxHeap ang mga elemento sa queue sa pagkakasunud-sunod ng root, left-child with root as parent, right-child with root as parent, left-child with first left-child as parent, right-child with first left- child as magulang, kanang-anak na may unang kanang-anak bilang magulang, kaliwang-anak na may unang kanang-anak bilang magulang atbp, na may kasunod na mga halaga gamit ang kaliwa at kanang mga anak bilang mga magulang sa parehong pagkakasunud-sunod tulad ng nasa itaas. Ang PriorityQueue method contains(J) ay ginagamit upang malaman kung ang isang partikular na elemento, J, ay nasa isang queue. Sa kasong ito hinahanap namin ang J = 10. Sa aming halimbawa, totoo na ito ay nasa pila kaya ito ay isinulat sa console bilang totoo. Ang isa pang paraan ng PriorityQueue , ang remove(J) ay pagkatapos ay ginagamit upang alisin ang J = 10 mula saQueue . Upang ilarawan ang higit pa sa functionality ng PriorityQueue , ang method poll() ay ginagamit upang alisin ang head element (maximum value) gamit ang isang while loop, sa bawat oras na inaalis ang head element sa bagong queue at binabawasan ang queue sa laki ng isa sa bawat oras. Nangyayari ito sa paraan ng writeQueuetinawag mula sa pangunahing. Sa bawat oras na ang elemento ay tinanggal ay naka-print sa console. Ang orihinal na pila ay sa kalaunan ay walang natitirang elemento. Ang mga naka-print na elemento ay ang max heap sa pababang pagkakasunud-sunod ng halaga, kung saan ang ulo ng queue ay naka-print out sa bawat oras.

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);
       }
   }

Output:

Max Heapify

Ang Max Heapify algorithm ay ginagamit upang matiyak na ang isang binary tree ay isang max heap. Kung tayo ay nasa isang node, n, at ang mga child node nito, kaliwa at kanan ay mga max na tambak din mismo, kung gayon mahusay, mayroon tayong max heap. Kung hindi ito ang kaso sa buong puno, wala tayong max heap. Ang Max Heapify algorithm ay ginagamit upang pagbukud-bukurin ang puno upang ito ay sumunod sa mga prinsipyo ng maxheap. Gumagana lang ang Max Heapify sa isang node. Kung ang kinakailangan ay ang array ay isang max heap array, ang lahat ng sub tree ay dapat na i-convert sa maxheap bago ang ugat, nang paisa-isa. Dapat gamitin ang algorithm sa bawat node. Gagawin ito sa N/2 node (ang mga dahon ay susunod sa max na kinakailangan ng heap). Ang pagiging kumplikado ng oras ng heap ay O(NlogN), at para sa isang node sa taas X, ang pagiging kumplikado ng oras ay O(X). Ang sumusunod na code ay nagpapakita kung paano maxheapify ang isang puno (isang array).

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();
       }
  }
}

Nagbibigay ng output: Sa code na ito, ang Array ay nilikha at puno ng mga numero. Ang pangalawang array, newArray , ay nilikha at sa pagkakataong ito ay maglalaman ito ng resulta ng pamamaraan, maxheapCreate , ang max heap array. Ang pamamaraan maxHeapCreate ay tinatawag mula sa main , at dito ang isang bagong array, theNewArr , ay nilikha at puno ng mga resulta ng maxHeapify . Ginagawa ito sa pamamagitan ng pag-loop sa kalahati ng laki ng input array. Para sa bawat pass ng loop, method maxHeapify , ay tinatawag na simula sa elemento sa gitna ng array at nagtatapos sa una. Para sa bawat tawag ng maxHeapify, ang kaliwang anak at kanang anak ng parent node, i, ay matatagpuan at ginagawa ang mga pagsusuri upang mahanap kung alin ang pinakamalaki sa tatlo, na tinutukoy iyon bilang maxVal . Kung ang maxVal ay hindi katumbas ng parent node, ang isang swap ay gagawin upang ang parent node at maxVal ay mapalitan at pagkatapos ay ang maxHeapify ay tatawagin muli sa oras na ito sa maxVal at ang parehong mga hakbang ay natupad tulad ng dati. Sa kalaunan ay malilikha ang max heap at wala nang mga pag-ulit na isasagawa. Ang na-update na array, array , ay ibinalik na ngayon sa pangunahing bilang newArray at pagkatapos ay ang bawat magkakasunod na elemento ay naka-print sa console. newArrayay isa na ngayong max heap. Tandaan, tulad ng sa nakaraang halimbawa gamit ang PriorityQueue ang mga numero ay nakasulat: ugat, kanang-anak ng ugat bilang magulang, kaliwa-anak ng ugat bilang magulang, kanang-anak ng unang kanan-anak bilang magulang, kaliwa-anak ng una kaliwa-anak bilang magulang, kanang-anak ng unang kaliwang-anak bilang magulang, kaliwang-anak ng unang kanang-anak bilang magulang, atbp. Ang mga ito ay nasa isang bahagyang naiibang pagkakasunud-sunod sa mga iyon kapag gumagamit ng PriorityQueue dahil ang paghahambing ay ginagawa sa pagitan ng magkakasunod na elemento samantalang sa halimbawa ng maxheapify, ang node ay inihambing sa susunod na dalawang sunud-sunod na elemento sa array at ipinagpalit para sa pinakamalaking halaga. Sa madaling salita, dalawang magkaibang algorithm ang ginagamit. Parehong gumagawa ng max heap.

Konklusyon

Kaya't dito ay tiningnan namin ang max heap at kung paano ito magagawa gamit ang alinman sa PriorityQueue o isang Max Heapify algorithm. Ang paggamit ng PriorityQueue na may reverseOrder() ay isang maayos na paraan ng paggawa nito at ang inirerekomendang paraan. Gayunpaman, maaari mong pag-aralan ang mga halimbawang ito at isulat ang iyong sariling mga pamamaraan dahil ito ay isang mahusay na pagsasanay sa pag-coding na tutulong sa iyo na magtagumpay sa iyong panayam para sa Java Junior.