Max Heap di Jawa

Pohon Biner

Di Jawa, ada banyak jenis struktur data. Tumpukan didasarkan pada struktur pohon yang disebut pohon biner . Pohon biner terdiri dari node, yang masing-masing dapat memiliki maksimal 2 node anak: Pohon biner terdiri dari node induk yang dapat memiliki 0 hingga 2 node. Ia dapat memiliki simpul anak kiri dan/atau simpul anak kanan, atau tanpa simpul sama sekali. Dalam pohon biner lengkap, semua node terisi kecuali level terakhir yang bisa penuh, tetapi tidak perlu penuh. Level terakhir, level ke-n, dapat memiliki 1 hingga 2n node, di mana yang pertama berada di n = 0 dan merupakan root.

Tumpukan Maks

Max heap (atau maxheap) adalah pohon biner lengkap . Hal penting tentang itu adalah bahwa simpul induk HARUS memiliki nilai lebih besar atau sama dengan simpul anak kiri dan kanan. Jika ini tidak dipatuhi, Anda tidak memiliki tumpukan maksimal. Min heap, di sisi lain, berlawanan dengan root sebagai nilai terkecil dengan node berturut-turut meningkat nilainya; setiap simpul anak memiliki nilai lebih besar atau sama dengan induknya. Ini juga merupakan pohon biner yang lengkap. Contoh max heap adalah: Max heap dapat dibangun dari array. Array ini akan dianggap sebagai pohon. Untuk heap, jika root, (simpul induk teratas dari pohon) disimpan pada posisi (indeks) n, itu didefinisikan untuk array, theArray , sebagai theArray[n]. Oleh karena itu, node anak kiri dan kanan masing-masing berada di Array[2n+1] dan Array[2n+2] . Untuk tumpukan maksimum, akarnya ada di theArray[0] . Untuk level n, root n = 0: theArr[n] adalah node induk theArr[(2*n)+1] adalah node anak kiri theArr[(2*n)+2] adalah node anak kanan

Kelas PriorityQueue

Tumpukan di Jawa dapat diimplementasikan menggunakan Kelas PriorityQueue . PriorityQueue digunakan untuk menemukan item yang paling atau kurang penting dalam sebuah koleksi. Kelas PriorityQueue dapat ditemukan di java.util.package . PriorityQueues harus dibentuk dari objek yang sebanding sehingga ditempatkan dalam urutan tertentu dalam antrian. PriorityQueue dapat memiliki pembanding sehingga dibuat perbandingan antara objek dan antrian yang terbentuk berdasarkan perbandingan ini. Contohnya adalah:

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

Memberikan keluaran: Dalam contoh ini, ukuran default intQueue adalah 11, jadi belum dinyatakan (biasanya argumen pertama sebelum pembanding) dan pembandingnya diberikan sebagai: Ini akan melakukan perbandingan antara item di intQueue dan mengurutkannya ke dalam panjang array urutan naik.

Implementasi PriorityQueue untuk Membuat Max Heap

Kelas PriorityQueue default ke min heap tanpa pembanding. Min heap adalah kebalikan dari max heap sehingga root adalah nilai terkecil dan node anak berturut-turut lebih besar atau sama dengan root dan node parental berikutnya. Untuk alasan ini, untuk tumpukan maksimum, perlu menggunakan reverseOrder() dari kerangka Koleksi Java sebagai pembanding. Ini akan memastikan kita mendapatkan tumpukan maksimum dan bukan tumpukan minimum. Kelas ini memiliki metode yang berguna seperti add() , contains() , remove() , poll() , dan peek() . Elemen ditambahkan ke antrean dan dapat dalam urutan apa pun. Antrean PriorityQueue baru akan menyimpan elemen tersebut sebagai tumpukan maksimum dalam urutan terbalik. Saat antrian ditulis, urutannya adalah: Root Anak kiri dengan root sebagai induk (Left-child_1) Anak kanan dengan root sebagai induk (Right-child_1) Anak kiri dengan Left-child_1 sebagai induk (Left-child_2 ) Anak kanan dengan anak kiri_1 sebagai orang tua (anak kanan_2) anak kiri dengan anak kanan_1 sebagai orang tua (anak kiri_3) anak kanan dengan anak kanan_1 sebagai orang tua (anak kanan_3) anak kiri dengan anak kiri_2 sebagai induk (Left-child_4) Right-child dengan Left-child_2 sebagai induk (Right-child_4), dllKode berikut adalah contoh bagaimana max heap (maxheap) dibuat di java. Hal pertama yang harus dilakukan adalah mengisi array dengan nilai yang akan dibuatkan max heap. Ini disebut Array . Selanjutnya, PriorityQueue , theQueue , dibuat dan kemudian elemen dari Array ditambahkan ke dalamnya. Ini menggunakan metode add() , misalnya theQueue.add(10) untuk menambahkan 10 ke akhir antrian. Untuk mengilustrasikan beberapa fungsionalitas Kelas PriorityQueue , metode peek() kemudian digunakan untuk menemukan kepala heap, dan ini adalah nilai maksimum, dalam hal ini, 99. Tugas selanjutnya adalah memeriksa ukuran heap menggunakan ukuran()yang ditemukan 9 dan ini dicetak ke konsol. Metode writeMaxHeap menulis elemen dalam antrian dalam urutan root, anak kiri dengan root sebagai orang tua, anak kanan dengan root sebagai orang tua, anak kiri dengan anak kiri pertama sebagai orang tua, anak kanan dengan anak kiri pertama sebagai orang tua parent, right-child dengan first right-child sebagai parent, left-child dengan first right-child sebagai parent dst, dengan nilai selanjutnya menggunakan left dan right children sebagai parent dengan urutan yang sama seperti di atas. Metode PriorityQueue contains(J) digunakan untuk mengetahui apakah elemen tertentu, J, berada dalam antrian . Dalam hal ini kita mencari J = 10. Dalam contoh kita, benar bahwa ini ada dalam antrean sehingga ini ditulis ke konsol sebagai benar. Metode PriorityQueue lainnya , remove(J) kemudian digunakan untuk menghapus J = 10 dari theQueue . Untuk lebih mengilustrasikan fungsionalitas PriorityQueue , metode poll() digunakan untuk menghapus elemen kepala (nilai maksimum) menggunakan perulangan while , setiap kali menghapus elemen kepala dalam antrean baru dan mengurangi ukuran antrean satu kali setiap kali. Ini terjadi dalam metode writeQueuedipanggil dari utama. Setiap kali elemen yang dihapus dicetak ke konsol. Antrean asli pada akhirnya tidak akan memiliki elemen yang tersisa. Elemen yang dicetak adalah tumpukan maksimum dalam urutan nilai yang menurun, di mana kepala antrean dicetak setiap waktu.

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

Keluaran:

Max Heapify

Algoritme Max Heapify digunakan untuk memastikan bahwa pohon biner adalah tumpukan maksimal. Jika kita berada di sebuah node, n, dan node anaknya, kiri dan kanan juga merupakan max heap, maka bagus, kita memiliki max heap. Jika ini tidak terjadi di seluruh pohon maka kita tidak memiliki tumpukan maksimal. Algoritma Max Heapify digunakan untuk mengurutkan pohon agar sesuai dengan prinsip maxheap. Max Heapify bekerja hanya pada satu node. Jika persyaratannya adalah array adalah maxheap array, maka semua sub pohon harus dikonversi ke maxheap sebelum root, satu per satu. Algoritma harus digunakan pada setiap node. Ini akan dilakukan pada N/2 node (dedaunan akan mematuhi persyaratan tumpukan maksimum). Kompleksitas waktu heap adalah O(NlogN), dan untuk satu node pada ketinggian X, kompleksitas waktunya adalah O(X). Kode berikut menunjukkan bagaimana memaksimalkan sebuah pohon (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();
       }
  }
}

Memberikan keluaran: Dalam kode ini, Array dibuat dan diisi dengan angka. Array kedua, newArray , dibuat dan kali ini berisi hasil dari metode, maxheapCreate , array max heap. Metode maxHeapCreate dipanggil dari main , dan di sini array baru, theNewArr , dibuat dan diisi dengan hasil maxHeapify . Ini dilakukan dengan mengulang lebih dari setengah ukuran array input. Untuk setiap lintasan loop, metode maxHeapify , dipanggil mulai dari elemen di tengah array dan diakhiri dengan yang pertama. Untuk setiap panggilan maxHeapify, anak kiri dan anak kanan dari simpul induk, i, ditemukan dan pemeriksaan dilakukan untuk menemukan mana yang terbesar dari ketiganya, mendefinisikannya sebagai maxVal . Jika maxVal tidak sama dengan parent node maka swap dilakukan sehingga parent node dan maxVal ditukar dan kemudian maxHeapify dipanggil lagi kali ini di maxVal dan langkah yang sama dilakukan seperti sebelumnya. Akhirnya tumpukan maksimum akan dibuat dan tidak akan ada lagi iterasi yang harus dilakukan. Array yang diperbarui, array , sekarang dikembalikan ke main sebagai newArray dan kemudian setiap elemen berurutan dicetak ke konsol. newArraysekarang menjadi tumpukan maksimal. Perhatikan, bahwa seperti pada contoh sebelumnya menggunakan PriorityQueue angka-angkanya ditulis: akar, anak kanan dari akar sebagai induk, anak kiri dari akar sebagai induk, anak kanan dari anak kanan pertama sebagai induk, anak kiri dari yang pertama anak kiri sebagai orang tua, anak kanan dari anak kiri pertama sebagai orang tua, anak kiri dari anak kanan pertama sebagai orang tua, dll. Urutannya sedikit berbeda dengan saat menggunakan PriorityQueue karena perbandingan dilakukan antara elemen berurutan sedangkan dalam contoh maxheapify, node dibandingkan dengan dua elemen berurutan berikutnya dalam array dan ditukar dengan nilai terbesar. Singkatnya, dua algoritma berbeda digunakan. Keduanya membuat tumpukan maksimal.

Kesimpulan

Jadi di sini kita telah melihat max heap dan bagaimana itu dapat dibuat dengan algoritma PriorityQueue atau Max Heapify. Menggunakan PriorityQueue dengan reverseOrder() adalah cara yang rapi untuk melakukan ini dan metode yang disarankan. Namun, Anda dapat mempelajari contoh-contoh ini dan menulis metode Anda sendiri karena ini akan menjadi latihan pengkodean yang baik yang membantu Anda berhasil dalam wawancara untuk Java Junior.