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:

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:
A 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