Max Heap di Jawa

Pokok Binari

Di Jawa, terdapat pelbagai jenis struktur data. Timbunan itu berdasarkan struktur pokok yang dipanggil pokok binari . Pokok binari terdiri daripada nod, setiap satunya boleh mempunyai maksimum 2 nod anak: Pokok binari terdiri daripada nod induk yang boleh mempunyai dari 0 hingga 2 nod. Ia boleh mempunyai nod anak kiri dan/atau nod anak kanan, atau tiada nod langsung. Dalam pokok binari yang lengkap, semua nod diisi kecuali tahap terakhir yang boleh penuh, tetapi tidak perlu penuh. Tahap terakhir, tahap ke-n, boleh mempunyai dari 1 hingga 2n nod, di mana yang pertama berada di n = 0 dan merupakan punca.

Timbunan Maks

Max timbunan (atau maxheap) ialah pokok binari yang lengkap . Perkara penting mengenainya ialah nod induk MESTI mempunyai nilai yang lebih besar daripada atau sama dengan nod anak kiri dan kanan. Jika ini tidak dipatuhi, anda tidak mempunyai timbunan maksimum. Tumpukan min, sebaliknya, adalah bertentangan dengan punca sebagai nilai terkecil dengan nod berturut-turut meningkat dalam nilai; setiap nod anak mempunyai nilai yang lebih besar daripada atau sama dengan induknya. Ia juga merupakan pokok binari yang lengkap. Contoh timbunan maks ialah: Timbunan maks boleh dibina daripada tatasusunan. Tatasusunan ini akan difikirkan dari segi pokok. Untuk timbunan, jika akar, (nod induk atas pokok) disimpan pada kedudukan (indeks) n, ia ditakrifkan untuk tatasusunan, theArray , sebagai theArray[n]. Oleh itu, nod anak kiri dan kanan berada pada Array[2n+1] dan Array[2n+2] masing-masing. Untuk timbunan maks, akar adalah di theArray[0] . Untuk tahap n, punca n = 0: theArr[n] ialah nod induk theArr[(2*n)+1] ialah nod anak kiri theArr[(2*n)+2] ialah nod anak kanan

Kelas PriorityQueue

Heaps dalam Java boleh dilaksanakan menggunakan Kelas PriorityQueue . PriorityQueues digunakan untuk mencari item yang paling atau paling kurang penting dalam koleksi.Kelas PriorityQueue boleh didapati dalam java.util.package . PriorityQueues mesti dibentuk daripada objek yang setanding supaya ia diletakkan dalam susunan tertentu dalam baris gilir. PriorityQueue boleh mempunyai pembanding supaya perbandingan antara objek dibuat dan baris gilir terbentuk mengikut perbandingan ini. Contohnya ialah:

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

Memberi output: Dalam contoh ini, saiz lalai intQueue ialah 11, jadi tidak dinyatakan (biasanya hujah pertama sebelum pembanding) dan pembanding telah diberikan sebagai: Ini akan melakukan perbandingan antara item dalam intQueue dan menyusunnya ke dalam panjang tatasusunan tertib menaik.

Pelaksanaan PriorityQueue untuk Mencipta Timbunan Maks

Kelas PriorityQueue lalai kepada timbunan min tanpa pembanding. Timbunan min adalah bertentangan dengan timbunan maks dan oleh itu punca ialah nilai terkecil dan nod anak berturut-turut adalah lebih besar atau sama dengan akar dan nod ibu bapa yang berikutnya. Atas sebab ini, untuk timbunan maks, adalah perlu untuk menggunakan reverseOrder() daripada rangka kerja Koleksi Java sebagai pembanding. Ini akan memastikan kita mendapat timbunan maks dan bukan timbunan min. Kelas ini mempunyai kaedah berguna seperti add() , contains() , remove() , poll() dan peek() . Elemen ditambah pada baris gilir dan boleh dalam sebarang susunan. Baris gilir PriorityQueue baharu akan menyimpan elemen tersebut sebagai timbunan maksimum dalam susunan terbalik. Apabila baris gilir ditulis, susunannya ialah: Root Kiri-anak dengan akar sebagai induk (Kiri-anak_1) Kanan-anak dengan akar sebagai induk (Kanan-anak_1) Kiri-anak dengan Kiri-anak_1 sebagai induk (Kiri-anak_2 ) Anak-kanan dengan anak-kiri_1 sebagai ibu bapa (anak-kanan_2) anak-kiri dengan anak-kanan_1 sebagai ibu bapa (anak-kiri_3) anak-kanan dengan anak-kanan_1 sebagai ibu bapa (anak-kanan_3) anak-kiri dengan anak-kiri_2 sebagai ibu bapa (Kanan-anak_4) Kanan-anak dengan Kiri-anak_2 sebagai ibu bapa (Kanan-anak_4), dllKod berikut ialah contoh bagaimana timbunan maks (maxheap) dibuat dalam java. Perkara pertama yang perlu dilakukan ialah mengisi tatasusunan dengan nilai yang timbunan maks akan dibuat. Ini dipanggil theArray . Seterusnya, PriorityQueue , theQueue , dicipta dan kemudian unsur-unsur daripada theArray ditambah kepada ini. Ini menggunakan kaedah add() , contohnya theQueue.add(10) untuk menambah 10 pada penghujung baris gilir. Untuk menggambarkan beberapa kefungsian Kelas PriorityQueue , kaedah peek() kemudiannya digunakan untuk mencari kepala timbunan, dan ini ialah nilai maksimum, dalam kes ini, 99. Tugas seterusnya ialah menyemak saiz timbunan menggunakan saiz()yang didapati 9 dan ini dicetak ke konsol. Kaedah writeMaxHeap menulis elemen dalam baris gilir mengikut urutan akar, anak kiri dengan akar sebagai induk, anak kanan dengan akar sebagai induk, anak kiri dengan anak kiri pertama sebagai ibu bapa, anak kanan dengan anak kiri pertama sebagai ibu bapa, anak kanan dengan anak kanan pertama sebagai ibu bapa, anak kiri dengan anak kanan pertama sebagai ibu bapa dsb, dengan nilai seterusnya menggunakan anak kiri dan kanan sebagai ibu bapa dalam susunan yang sama seperti di atas. Kaedah PriorityQueue mengandungi(J) digunakan untuk mengetahui sama ada elemen tertentu, J, berada dalam baris gilir . Dalam kes ini kita mencari J = 10. Dalam contoh kita, adalah benar bahawa ini dalam baris gilir jadi ini ditulis kepada konsol sebagai benar. Kaedah PriorityQueue yang lain , remove(J) kemudiannya digunakan untuk mengalih keluar J = 10 daripada theQueue . Untuk menggambarkan lebih banyak fungsi PriorityQueue , kaedah poll() digunakan untuk mengalih keluar elemen kepala (nilai maksimum) menggunakan gelung sementara , setiap kali mengalih keluar elemen kepala dalam baris gilir baharu dan mengurangkan saiz baris gilir sebanyak satu setiap kali. Ini berlaku dalam kaedah writeQueuedipanggil dari utama. Setiap kali elemen yang dialih keluar dicetak ke konsol. Baris gilir asal akhirnya tidak akan mempunyai unsur yang tersisa. Elemen yang dicetak ialah timbunan maksimum dalam tertib nilai menurun, di mana kepala baris gilir dicetak keluar setiap kali.

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

Pengeluaran:

Max Heapify

Algoritma Max Heapify digunakan untuk memastikan pokok binari ialah timbunan maksimum. Jika kita berada di nod, n, dan nod anaknya, kiri dan kanan juga adalah timbunan maks, maka hebat, kita mempunyai timbunan maks. Jika ini tidak berlaku di seluruh pokok maka kami tidak mempunyai timbunan maksimum. Algoritma Max Heapify digunakan untuk mengisih pokok supaya ia mematuhi prinsip maxheap. Max Heapify berfungsi pada satu nod sahaja. Jika keperluannya ialah tatasusunan ialah tatasusunan timbunan maks, maka semua sub pokok mesti ditukar kepada timbunan maks sebelum akar, satu demi satu. Algoritma mesti digunakan pada setiap nod. Ini akan dilakukan pada N/2 nod (daun akan mematuhi keperluan timbunan maksimum). Kerumitan masa timbunan ialah O(NlogN), dan untuk satu nod pada ketinggian X, kerumitan masa ialah O(X). Kod berikut menunjukkan cara untuk memaksimumkan pokok (tatasusunan).

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

Memberi output: Dalam kod ini, theArray dicipta dan diisi dengan nombor. Tatasusunan kedua, newArray , dicipta dan kali ini ia akan mengandungi hasil kaedah, maxheapCreate , tatasusunan timbunan maks. Kaedah maxHeapCreate dipanggil dari main , dan di sini tatasusunan baharu, theNewArr , dicipta dan diisi dengan hasil maxHeapify . Ini dilakukan dengan menggelungkan lebih separuh saiz tatasusunan input. Untuk setiap pas gelung, kaedah maxHeapify , dipanggil bermula pada elemen di tengah tatasusunan dan berakhir dengan yang pertama. Untuk setiap panggilan maxHeapify, anak kiri dan anak kanan nod induk, i, ditemui dan semakan dilakukan untuk mencari yang mana yang terbesar daripada tiga, mentakrifkannya sebagai maxVal . Jika maxVal tidak sama dengan nod induk maka swap dilakukan supaya nod induk dan maxVal ditukar dan kemudian maxHeapify dipanggil semula kali ini pada maxVal dan langkah yang sama dijalankan seperti sebelumnya. Akhirnya timbunan maks akan dibuat dan tidak akan ada lagi lelaran untuk dijalankan. Tatasusunan yang dikemas kini, tatasusunan , kini dikembalikan kepada utama sebagai newArray dan kemudian setiap elemen berturut-turut dicetak ke konsol. newArraykini adalah timbunan maksimum. Perhatikan, seperti dalam contoh sebelumnya menggunakan PriorityQueue, nombor ditulis: akar, anak kanan akar sebagai induk, kiri-anak akar sebagai induk, kanan-anak kanan pertama sebagai induk, kiri-anak pertama anak kiri sebagai ibu bapa, anak kanan kepada anak kiri pertama sebagai ibu bapa, anak kiri anak kanan pertama sebagai ibu bapa, dsb. Mereka berada dalam susunan yang sedikit berbeza daripada mereka apabila menggunakan PriorityQueue kerana perbandingan dilakukan antara elemen berturut - turut manakala dalam contoh maxheapify, nod dibandingkan dengan dua elemen berturut-turut seterusnya dalam tatasusunan dan ditukar untuk nilai terbesar. Ringkasnya, dua algoritma berbeza digunakan. Kedua-duanya mencipta timbunan maksimum.

Kesimpulan

Jadi di sini kita telah melihat timbunan maks dan cara ia boleh dibuat dengan sama ada algoritma PriorityQueue atau algoritma Max Heapify. Menggunakan PriorityQueue dengan reverseOrder() ialah cara yang kemas untuk melakukan ini dan kaedah yang disyorkan. Walau bagaimanapun, anda boleh mengkaji contoh ini dan menulis kaedah anda sendiri kerana ini akan menjadi latihan pengekodan yang baik untuk membantu anda berjaya dalam temu duga anda untuk Java Junior.