Det binära trädet
I Java finns det många olika typer av datastrukturer. Högen är baserad på en trädstruktur som kallas ett binärt träd . Ett binärt träd består av noder, som var och en kan ha maximalt 2 underordnade noder: Ett binärt träd består av en föräldernod som kan ha från 0 till 2 noder. Den kan ha en vänster-under-nod och/eller en höger-under-nod, eller inga noder alls. I ett komplett binärt träd är alla noder fyllda förutom den sista nivån som kan vara full, men inte behöver vara full. Den sista nivån, den n:e nivån, kan ha från 1 till 2n noder, där den första är vid n = 0 och är roten.Max Heap
Max heap (eller maxheap) är ett komplett binärt träd . Det viktiga med det är att föräldranoden MÅSTE ha ett värde som är större än eller lika med det för vänster- och högerundernoderna. Om detta inte följs har du ingen maxhög. Min heap, å andra sidan, är motsatsen med roten som det minsta värdet med successiva noder som ökar i värde; varje underordnad nod har ett värde som är större än eller lika med dess överordnade. Det är också ett komplett binärt träd. Ett exempel på en maxhög är: Maxhög kan byggas från en array. Denna array kommer att ses som ett träd. För en hög, om roten, (trädets översta överordnade nod) är lagrad i position (index) n, definieras den för array, theArray , som theArray[n]. De vänstra och högra underordnade noderna är därför vid theArray[2n+1] respektive theArray[2n+2] . För maxhögen är roten vid theArray[0] . För nivån n är roten n = 0: theArr[n] är föräldernoden theArr[(2*n)+1] är den vänstra underordnade noden theArr[(2*n)+2] är den högra barnnodenKlassen PriorityQueue
Heaps i Java kan implementeras med PriorityQueue Class. PriorityQueue används för att hitta det viktigaste eller minst viktiga föremålet i en samling. Klassen PriorityQueue finns i java.util.package . Prioritetsköer måste bildas av objekt som är jämförbara så att de placeras i en viss ordning i kön. PriorityQueue kan ha en komparator så att en jämförelse mellan objekten görs och den kön som bildas enligt denna jämförelse. Ett exempel är: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());
}
}
}
Ge utdata:
1 3 6 7 11
I det här exemplet är standardstorleken för intQueue 11, så har inte angetts (vanligtvis det första argumentet före komparatorn) och komparatorn har angetts som:
(a,b) -> a - b
Detta kommer att göra en jämförelse mellan objekten i intQueue och sortera dem i arraylängder i stigande ordning.
Implementering av PriorityQueue för att skapa en Max Heap
PriorityQueue Class är standard till min heap utan en komparator. Minhög är motsatsen till maxhög och så roten är det minsta värdet och på varandra följande underordnade noder är större eller lika med roten och efterföljande föräldranoder. Av denna anledning, för max heap, är det nödvändigt att använda reverseOrder() från Javas samlingsramverk som komparator. Detta kommer att säkerställa att vi får en maxhög och inte en minhög. Den här klassen har användbara metoder som add() , contains() , remove() , poll() , och peek() .Metod | Beskrivning | Tidskomplexitet |
---|---|---|
add(J) | Lägger till element J i slutet av trädet | O(LogN) |
ta bort(J) | Ta bort värdet J från trädet | PÅ) |
opinionsundersökning() | Tar bort maximalt element av träd | O(LogN) |
titt() | Returnerar rotelementet överst i trädet | O(1) |
innehåller(J) | Returnerar sant om J står i kön, falskt om inte | PÅ) |
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);
}
}
Produktion:
99 Storlek på kön? 9 kön skriven med för loop 99 51 19 13 10 5 6 3 9 Innehåller kön 10? true theQueue skrivet ut med poll() 99 51 19 13 9 6 5 3 Storlek på kön? 0
Max Heapify
Max Heapify-algoritmen används för att säkerställa att ett binärt träd är en maxhög. Om vi är vid en nod, n, och dess undernoder, vänster och höger är också maxhögar själva, så bra, vi har en maxhög. Om så inte är fallet i hela trädet så har vi ingen maxhög. Max Heapify-algoritmen används för att sortera trädet så att det följer maxheap-principerna. Max Heapify fungerar bara på en nod. Om kravet är att arrayen är en maxheap-array, måste alla underträd konverteras till maxheap före roten, ett i taget. Algoritmen måste användas på varje nod. Detta kommer att göras på N/2 noder (löven kommer att följa maxkraven för högen). Tidskomplexiteten för högen är O(NlogN), och för en nod på höjden X är tidskomplexiteten O(X). Följande kod visar hur man maxheapify ett träd (en 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();
}
}
}
Ge utdata:
newArray:99 51 19 10 3 13 65 9 rot: 99 föräldernod: 99 vänster barn: 51 höger barn:19 föräldernod: 51 vänster barn: 10 höger barn:3 föräldernod: 19 vänster barn: 13 höger barn:6 föräldernod: 10 vänster barn: 5 höger barn :999999999 föräldernod: 99 vänster barn: 51 höger barn:19 föräldernod: 51 vänster barn: 10 höger barn:3 föräldernod: 19 vänster barn: 13 höger barn:6 föräldernod: 10 vänster barn: 5 höger barn: 999 föräldernod: 99 vänster barn: 51 höger barn:19 föräldernod: 51 vänster barn: 10 höger barn:3 föräldernod: 19 vänster barn: 13 höger barn:6 föräldernod: 10 vänster barn: 5 höger barn: 96 föräldernod: 10 vänster barn: 5 höger barn: 96 föräldernod: 10 vänster barn: 5 höger barn: 9
I den här koden skapas theArray och fylls med siffror. En andra array, newArray , skapas och den här gången kommer den att innehålla resultatet av metoden maxheapCreate , max heap arrayen. Metoden maxHeapCreate anropas från main , och här skapas en ny array, theNewArr , som fylls med maxHeapify- resultaten. Detta görs genom att loopa över halva storleken på inmatningsmatrisen. För varje pass av loopen kallas metoden maxHeapify , som börjar vid elementet i mitten av arrayen och slutar med det första. För varje samtal av maxHeapify, vänstra underordnade och högra underordnade underordnade noden, i, hittas och kontroller görs för att hitta vilken som är störst av de tre, och definierar det som maxVal . Om maxVal inte är lika med föräldernoden så görs ett byte så att föräldernoden och maxVal byts ut och sedan anropas maxHeapify igen denna gång på maxVal och samma steg utförs som tidigare. Så småningom kommer maxhögen att skapas och det kommer inte att finnas fler iterationer att utföra. Den uppdaterade arrayen, array , returneras nu till main som newArray och sedan skrivs varje på varandra följande element ut till konsolen. newArrayär nu en maxhög. Notera att som i det föregående exemplet med PriorityQueue skrivs siffrorna ut: rot, höger-barn till rot som förälder, vänster-barn till rot som förälder, höger-barn till första höger-barn som förälder, vänster-barn till första vänster-barn som förälder, höger-barn till första vänster-barn som förälder, vänster-barn till första höger-barn som förälder, etc. De är i en något annorlunda ordning än när man använder PriorityQueue eftersom jämförelsen görs mellan på varandra följande element medan i exemplet maxheapify jämförs noden med nästa två på varandra följande element i arrayen och byts ut mot det största värdet. Kort sagt, två olika algoritmer används. Båda skapar en maxhög.