A bináris fa
A Java-ban sokféle adatstruktúra létezik. A kupac egy bináris fának nevezett fastruktúrán alapul . A bináris fa csomópontokból áll, amelyek mindegyikének legfeljebb 2 gyermekcsomópontja lehet: A bináris fa egy szülőcsomópontból áll, amelynek 0-2 csomópontja lehet. Lehet benne bal oldali gyermek csomópont és/vagy jobb oldali gyermek csomópont, vagy egyáltalán nem. Egy teljes bináris fában az összes csomópont ki van töltve, kivéve az utolsó szintet, amely lehet tele, de nem kell tele lennie. Az utolsó, az n-edik szint 1-2n csomópontot tartalmazhat, ahol az első n = 0-nál van, és a gyökér.Max Heap
A Max heap (vagy maxheap) egy teljes bináris fa . A lényeg az, hogy a szülőcsomópontnak nagyobb vagy egyenlő értékkel kell rendelkeznie, mint a bal és a jobb oldali gyermek csomópont értéke. Ha ezt nem tartják be, akkor nincs max kupacod. Ezzel szemben a min kupac ennek az ellenkezője, ahol a gyökér a legkisebb érték, és az egymást követő csomópontok értéke nő; minden gyermek csomópont értéke nagyobb vagy egyenlő, mint a szülője. Ez is egy teljes bináris fa. Példa a max kupacra: Max kupac építhető tömbből. Ezt a tömböt faként fogjuk felfogni. Egy kupac esetében, ha a gyökér (a fa legfelső szülőcsomópontja) az n pozícióban (index) van tárolva, akkor a tömbhöz, a tömbhöz, mint Tömb [n] van megadva.. A bal és a jobb oldali gyermekcsomópont tehát a Tömb[2n+1] , illetve a Tömb[2n+2] pontban található. A max kupac esetén a gyökér a theArray[0] helyen van . Az n szintnél az n gyökér = 0: azArr[n] a szülőcsomópont az Arr[(2*n)+1] a bal oldali gyermekcsomópont az Arr[(2*n)+2] a jobb gyermekcsomópontA PriorityQueue osztály
A Java kupacok a PriorityQueue osztály használatával valósíthatók meg . A PriorityQueues a gyűjtemény legfontosabb vagy legkevésbé fontos elemeinek megtalálására szolgál. A PriorityQueue osztály a java.util.package fájlban található . A PriorityQueues-t olyan objektumokból kell kialakítani, amelyek összehasonlíthatók, hogy meghatározott sorrendbe kerüljenek a sorban. A PriorityQueue-nek lehet egy összehasonlítója, így az objektumok összehasonlítása és a sor ennek az összehasonlításnak megfelelően jön létre. Példa erre:
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());
}
}
}
Kimenet adása:
1 3 6 7 11
Ebben a példában az intQueue alapértelmezett mérete 11, ezért nincs megadva (általában az első argumentum a komparátor előtt), és a komparátor a következőképpen van megadva:
(a,b) -> a - b
Ez összehasonlítja az intQueue- ben lévő elemeket , és növekvő sorrendben rendezi őket tömbhosszúságokba.
A PriorityQueue megvalósítása maximális kupac létrehozásához
A PriorityQueue osztály alapértelmezés szerint min kupac, összehasonlító nélkül. A min kupac a max kupac ellentéte, így a gyökér a legkisebb érték, és az egymást követő gyermekcsomópontok nagyobbak vagy egyenlőek a gyökérrel és az azt követő szülői csomópontokkal. Emiatt a max heap esetén a Java Collections keretrendszeréből származó reverseOrder() függvényt kell használni összehasonlítóként. Ez biztosítja, hogy max kupacot kapjunk, és nem minimális kupacot. Ez az osztály olyan hasznos metódusokkal rendelkezik, mint az add() , include() , remove() , poll() és peek() .Módszer | Leírás | Idő összetettsége |
---|---|---|
add (J) | Hozzáadja a J elemet a fa végéhez | O(LogN) |
eltávolítás (J) | Távolítsa el a J értéket a fából | TOVÁBB) |
közvélemény kutatás() | Eltávolítja a fa maximális elemét | O(LogN) |
kandikál() | A gyökérelemet adja vissza a fa tetején | O(1) |
tartalmaz (J) | Igazat ad vissza, ha J benne van a sorban, hamis értéket, ha nem | TOVÁBB) |
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);
}
}
Kimenet:
99 A várólista mérete? 9 theQueue a for ciklus használatával írva 99 51 19 13 10 5 6 3 9 Tartalmaz a Queue 10-et? igaz theQueue kiírva poll() segítségével 99 51 19 13 9 6 5 3 A várólista mérete? 0
Max Heapify
A Max Heapify algoritmust arra használjuk, hogy biztosítsuk, hogy egy bináris fa maximális kupac legyen. Ha egy csomópontnál vagyunk, az n és a gyermek csomópontok, a bal és a jobb is max kupacok, akkor remek, van egy max kupacunk. Ha ez nem így van az egész fában, akkor nincs max kupacunk. A Max Heapify algoritmus a fa rendezésére szolgál, hogy az megfeleljen a maxheap elveknek. A Max Heapify csak egy csomóponton működik. Ha az a követelmény, hogy a tömb max. kupac tömb legyen, akkor az összes alfát a gyökér előtt maxheap-re kell konvertálni, egyenként. Az algoritmust minden csomóponton alkalmazni kell. Ez N/2 csomóponton történik (a levelek megfelelnek a maximális kupac követelményeknek). A kupac időbonyolultsága O(NlogN), egy X magasságú csomópont esetén pedig O(X). A következő kód megmutatja, hogyan lehet maximalizálni egy fát (tömböt).
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();
}
}
}
Kimenet adása:
newArray:99 51 19 10 3 13 65 9 gyökér : 99 szülő csomópont : 99 bal gyermek : 51 jobb gyermek :19 szülő csomópont : 51 bal gyermek : 10 jobb gyermek :3 szülő csomópont : 19 bal gyermek : 13 jobb gyermek :6 szülő csomópont : 10 bal gyermek : 5 jobb gyerek :999999999 szülőcsomópont : 99 bal gyermek : 51 jobb gyermek :19 szülő csomópont : 51 bal gyermek : 10 jobb gyermek :3 szülőcsomópont : 19 bal gyermek : 13 jobb gyermek :6 szülő csomópont : 10 bal gyermek : 5 jobb gyermek :999 szülőcsomópont : 99 bal gyermek : 51 jobb gyermek :19 szülő csomópont : 51 bal gyermek : 10 jobb gyermek :3 szülőcsomópont : 19 bal gyermek : 13 jobb gyermek :6 szülő csomópont : 10 bal gyermek : 5 jobb gyermek :96 szülőcsomópont : 10 bal gyermek : 5 jobb gyermek :96 szülőcsomópont : 10 bal gyermek : 5 jobb gyermek :9
Ebben a kódban a tömb jön létre, és számokkal van kitöltve. Létrejön egy második tömb, a newArray , amely ezúttal a maxheapCreate metódus eredményét fogja tartalmazni , a max kupactömböt. A maxHeapCreate metódus meghívása a main -ból történik , és itt egy új tömb, a theNewArr jön létre, és kitöltődik a maxHeapify eredményekkel. Ez úgy történik, hogy a bemeneti tömb méretének több mint felét hurkolja. A ciklus minden egyes lépésénél a maxHeapify metódus meghívása a tömb közepén lévő elemtől kezdődik és az elsővel végződik. A maxHeapify minden egyes hívásához, a szülőcsomópont bal és jobb gyermeke, i, megkeresésre kerül, és ellenőrzik, hogy melyik a legnagyobb a három közül, ezt maxValként határozva meg . Ha a maxVal nem egyenlő a szülőcsomóponttal, akkor csere történik, így a szülőcsomópont és a maxVal felcserélődik, majd a maxHeapify ezúttal is meghívásra kerül a maxVal- on , és ugyanazokat a lépéseket hajtja végre, mint korábban. Végül létrejön a maximális kupac, és nem kell több iterációt végrehajtani. A frissített tömb, a tömb , most newArray néven kerül vissza a főbe , majd minden egymást követő elemet kinyomtat a konzolra. newArraymost egy max kupac. Vegye figyelembe, hogy az előző példához hasonlóan a PriorityQueue használatával a számok ki vannak írva: gyökér, gyökér jobb gyermeke szülőként, gyökér bal gyermeke szülőként, első jobb gyermek jobb gyermeke szülőként, első bal gyermeke bal-gyermek szülőként, jobb-gyermek első bal-gyermek szülőként, bal-gyermek első jobb-gyermek szülőként stb. Ezek kissé eltérő sorrendben vannak, mint a PriorityQueue használatakor, mivel az összehasonlítás az egymást követő elemek között történik míg a maxheapify példában a csomópont összehasonlításra kerül a tömb következő két egymást követő elemével, és a legnagyobb értékre cseréli. Röviden, két különböző algoritmust használnak. Mindkettő maximális kupacot hoz létre.
GO TO FULL VERSION