Java'da Maksimum Yığın

İkili Ağaç

Java'da birçok farklı türde veri yapısı vardır. Yığın , ikili ağaç adı verilen bir ağaç yapısına dayanır . İkili ağaç, her biri en fazla 2 alt düğüme sahip olabilen düğümlerden oluşur: İkili ağaç, 0 ila 2 düğüme sahip olabilen bir ana düğümden oluşur. Bir sol alt düğüme ve/veya bir sağ alt düğüme sahip olabilir veya hiç düğüm olmayabilir. Tam bir ikili ağaçta, dolu olabilen ancak dolu olması gerekmeyen son seviye dışında tüm düğümler doludur. Son seviye, n'inci seviye, 1 ila 2n düğüme sahip olabilir, burada birincisi n = 0'dadır ve köktür.

Maksimum Yığın

Max yığın (veya maxheap) tam bir ikili ağaçtır . Bununla ilgili önemli olan şey, üst düğümün sol ve sağ alt düğümlerinkinden daha büyük veya ona eşit bir değere sahip OLMALIDIR. Buna uyulmazsa, maksimum yığınız olmaz. Öte yandan min yığın, değeri artan ardışık düğümlerle en küçük değer olarak kökün tersidir; her alt düğüm, ebeveyninden büyük veya ona eşit bir değere sahiptir. Aynı zamanda tam bir ikili ağaçtır. Maksimum yığına bir örnek: Maksimum yığın bir diziden oluşturulabilir. Bu dizilim bir ağaç olarak düşünülecektir. Bir yığın için, kök (ağacın en üst üst düğümü) n konumunda (dizin) depolanıyorsa, theArray dizisi için theArray[n] olarak tanımlanır. Sol ve sağ alt düğümler bu nedenle sırasıyla Array[2n+1] ve Array[2n+2]' dedir . Maksimum yığın için, kök theArray[0] konumundadır . n düzeyi için, kök n = 0: theArr[n] üst düğümdür theArr[(2*n)+1] sol alt düğümdür theArr[(2*n)+2] sağ alt düğümdür

PriorityQueue Sınıfı

Java'daki yığınlar, PriorityQueue Sınıfı kullanılarak uygulanabilir . PriorityQueu'ler, bir koleksiyondaki en önemli veya en az önemli öğeyi bulmak için kullanılır. PriorityQueue sınıfı, java.util.package içinde bulunabilir . PriorityQueues, kuyruğa belirli bir sıraya yerleştirilmeleri için karşılaştırılabilir nesnelerden oluşturulmalıdır. PriorityQueue bir karşılaştırıcıya sahip olabilir, böylece nesneler arasında bir karşılaştırma yapılır ve bu karşılaştırmaya göre sıra oluşturulur. Bir örnek:

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

Çıktı vermek: Bu örnekte, intQueue'nun varsayılan boyutu 11'dir, bu nedenle belirtilmemiştir (genellikle karşılaştırıcıdan önceki ilk argüman) ve karşılaştırıcı şu şekilde verilmiştir: Bu, intQueue'deki öğeler arasında bir karşılaştırma yapacak ve onu artan düzende dizi uzunluklarına göre sıralayacaktır.

Maksimum Yığın Oluşturmak için PriorityQueue Uygulaması

PriorityQueue Sınıfı varsayılan olarak bir karşılaştırıcı olmadan en az öbektir . Min yığın, maksimum yığının tersidir ve bu nedenle kök en küçük değerdir ve ardışık alt düğümler, kök ve sonraki ebeveyn düğümlerinden daha büyük veya ona eşittir. Bu nedenle, maksimum yığın için karşılaştırıcı olarak Java'nın Koleksiyonlar çerçevesinden reverseOrder() işlevinin kullanılması gerekir . Bu, minimum yığın değil, maksimum yığın elde etmemizi sağlayacaktır. Bu Sınıf, add() , include() , remove() , poll() ve peek() gibi yararlı yöntemlere sahiptir . Öğeler kuyruğa eklenir ve herhangi bir sırada olabilir. Yeni PriorityQueue sırası, bu öğeleri maksimum yığın olarak ters sırada saklayacaktır. Sıra yazıldığında, sıra şu şekilde olacaktır: Kök Ebeveyn olarak kök ile sol çocuk (Sol-çocuk_1) Ebeveyn olarak kök ile sağ çocuk (Sağ-çocuk_1) Ebeveyn olarak Sol-çocuk_1 ile sol çocuk (Sol-çocuk_2) ) Ebeveyn olarak Left-child_1 ile sağ-çocuk (Right-child_2) Ebeveyn olarak Sağ-child_1 ile sol-çocuk (Left-child_3) Ebeveyn olarak Sağ-child_1 ile sağ-çocuk (Right-child_3) Sol-child_2 ile Sol-çocuk ebeveyn olarak (Sol-çocuk_4) Sağ-çocuk ve ebeveyn olarak Sol-çocuk_2 (Sağ-çocuk_4), vb.Aşağıdaki kod, Java'da bir maksimum yığının (maxheap) nasıl oluşturulduğuna bir örnektir. Yapılacak ilk şey, maksimum yığının oluşturulacağı değerlerle bir diziyi doldurmaktır. Buna Array denir . Ardından, bir PriorityQueue , theQueue oluşturulur ve ardından buna theArray öğesinden öğeler eklenir. Bu , sıranın sonuna 10 eklemek için add() yöntemini kullanır , örneğin theQueue.add(10) . PriorityQueue Sınıfının bazı işlevlerini göstermek için , peek() yöntemi yığının başını bulmak için kullanılır ve bu maksimum değerdir, bu durumda 99'dur. Bir sonraki görev, yığının boyutunu kontrol etmektir. size() kullanarak9 olarak bulunur ve bu konsola yazdırılır. Yöntem writeMaxHeap, sıradaki öğeleri kök sırasına göre yazar, sol-çocuk, kökü ebeveyn olarak, sağ-çocuk, kökü ebeveyn olarak, sol-çocuk, ilk sol-çocuk ebeveyn olarak, sağ-çocuk, ilk sol-çocuk olarak yazar ebeveyn, sağ-çocuk, ebeveyn olarak ilk sağ-çocuk, ebeveyn olarak ilk sağ-çocuk ile sol-çocuk vb., sonraki değerler sol ve sağ çocukları yukarıdaki sırayla ebeveyn olarak kullanır. PriorityQueue yöntemi içerir(J), belirli bir öğenin, J'nin bir kuyrukta olup olmadığını bulmak için kullanılır. Bu durumda J = 10'u ararız. Örneğimizde bunun kuyrukta olduğu doğru olduğundan konsola doğru olarak yazılır. Başka bir PriorityQueue yöntemi olan remove(J) , J = 10'u theQueue öğesinden kaldırmak için kullanılır . PriorityQueue işlevinin daha fazla işlevselliğini göstermek için , bir while döngüsü kullanarak baş öğeyi (maksimum değer) kaldırmak için poll() yöntemi kullanılır ; her seferinde baş öğe yeni kuyrukta kaldırılır ve kuyruğun boyutu her seferinde bir azaltılır. Bu, writeQueue yönteminde olurana telefondan arandı. Kaldırılan öğe her seferinde konsola yazdırılır. Orijinal sıra sonunda hiç öğe kalmayacak. Yazdırılan öğeler, her seferinde kuyruğun başının yazdırıldığı, azalan değer sırasına göre maksimum yığındır.

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

Çıktı:

Maksimum Yığınlaştırma

Max Heapify algoritması, bir ikili ağacın maksimum yığın olmasını sağlamak için kullanılır. Bir düğümdeysek, n ​​ve onun alt düğümleri, sol ve sağ da maksimum yığınlar, o zaman harika, maksimum yığınımız var. Ağaç boyunca durum böyle değilse, maksimum yığınımız olmaz. Max Heapify algoritması, ağacı maxheap ilkelerine uyacak şekilde sıralamak için kullanılır. Max Heapify yalnızca bir düğümde çalışır. Gereksinim, dizinin bir maksimum yığın dizisi olmasıysa, kökten önce tüm alt ağaçların teker teker maxheap'e dönüştürülmesi gerekir. Algoritma her düğümde kullanılmalıdır. Bu, N/2 düğümlerinde yapılacaktır (yapraklar maksimum yığın gereksinimlerine uyacaktır). Yığının zaman karmaşıklığı O(NlogN)'dir ve X yüksekliğindeki bir düğüm için zaman karmaşıklığı O(X)'dir. Aşağıdaki kod, bir ağacın (bir dizi) nasıl maksimize edileceğini gösterir.

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

Çıktı vermek: Bu kodda, Dizi oluşturulur ve sayılarla doldurulur. İkinci bir dizi, newArray oluşturulur ve bu sefer maxheapCreate yönteminin sonucunu , maksimum yığın dizisini içerecektir . maxHeapCreate yöntemi main'den çağrılır ve burada yeni bir dizi theNewArr oluşturulur ve maxHeapify sonuçlarıyla doldurulur. Bu, girdi dizisi boyutunun yarısından fazlasını döngüye sokarak yapılır. Döngünün her geçişi için, maxHeapify yöntemi , dizinin ortasındaki öğeden başlayıp ilkiyle biten olarak adlandırılır. Her maxHeapify çağrısı için, üst düğümün sol çocuğu ve sağ çocuğu i bulunur ve hangisinin en büyük olduğunu bulmak için kontroller yapılır ve bunu maxVal olarak tanımlar . Eğer maxVal, ana düğüme eşit değilse, o zaman bir takas yapılır, böylece ana düğüm ve maxVal yer değiştirir ve ardından bu kez maxVal üzerinde maxHeapify tekrar çağrılır ve önceki adımların aynısı yapılır. Sonunda maksimum yığın oluşturulacak ve gerçekleştirilecek başka yineleme olmayacak. Güncellenen dizi, şimdi main'e newArray olarak döndürülür ve ardından ardışık her öğe konsola yazdırılır. yeni dizişimdi bir maksimum yığın. PriorityQueue kullanan önceki örnekte olduğu gibi, sayıların yazıldığına dikkat edin: kök, kökün sağ çocuğu ebeveyn olarak, kökün sol çocuğu ebeveyn olarak, ilk sağ çocuğun sağ çocuğu ebeveyn olarak, ilkin sol çocuğu ebeveyn olarak sol-çocuk, ebeveyn olarak ilk sol-çocuğun sağ-çocuğu, ebeveyn olarak ilk sağ-çocuğun sol-çocuğu vb . Karşılaştırma ardışık öğeler arasında yapıldığından, PriorityQueue kullanıldığındakilerden biraz farklı bir sıradadırlar. oysa maxheapify örneğinde, düğüm dizideki sonraki iki ardışık öğeyle karşılaştırılır ve en büyük değerle değiştirilir. Kısaca iki farklı algoritma kullanılmaktadır. Her ikisi de bir maksimum yığın oluşturur.

Çözüm

Bu yüzden burada maksimum yığına ve bunun bir PriorityQueue veya Max Heapify algoritması ile nasıl oluşturulabileceğine baktık . PriorityQueue'yu reverseOrder() ile kullanmak, bunu yapmanın zarif bir yoludur ve önerilen yöntemdir. Ancak, bu örnekleri inceleyebilir ve kendi yöntemlerinizi yazabilirsiniz çünkü bu, Java Junior görüşmenizde başarılı olmanıza yardımcı olacak iyi bir kodlama alıştırması olacaktır.