బైనరీ ట్రీ
జావాలో, అనేక రకాల డేటా స్ట్రక్చర్‌లు ఉన్నాయి. కుప్ప బైనరీ ట్రీ అని పిలువబడే చెట్టు నిర్మాణంపై ఆధారపడి ఉంటుంది . బైనరీ ట్రీ నోడ్‌లను కలిగి ఉంటుంది, వీటిలో ప్రతి ఒక్కటి గరిష్టంగా 2 చైల్డ్ నోడ్‌లను కలిగి ఉంటుంది:
బైనరీ ట్రీ 0 నుండి 2 నోడ్‌లను కలిగి ఉండే పేరెంట్ నోడ్‌ను కలిగి ఉంటుంది. ఇది ఎడమ-చైల్డ్ నోడ్ మరియు/లేదా కుడి-చైల్డ్ నోడ్ లేదా నోడ్‌లను కలిగి ఉండకపోవచ్చు. పూర్తి బైనరీ ట్రీలో, చివరి స్థాయి మినహా అన్ని నోడ్‌లు నిండి ఉంటాయి, కానీ పూర్తి కానవసరం లేదు. చివరి స్థాయి, nవ స్థాయి, 1 నుండి 2n నోడ్‌లను కలిగి ఉంటుంది, ఇక్కడ మొదటిది n = 0 వద్ద ఉంటుంది మరియు ఇది రూట్.
గరిష్ట కుప్ప
మాక్స్ హీప్ (లేదా మాక్స్‌హీప్) అనేది పూర్తి బైనరీ చెట్టు . దాని గురించి ముఖ్యమైన విషయం ఏమిటంటే, పేరెంట్ నోడ్ ఎడమ మరియు కుడి-చైల్డ్ నోడ్‌ల కంటే ఎక్కువ లేదా సమానమైన విలువను కలిగి ఉండాలి. ఇది కట్టుబడి ఉండకపోతే, మీ వద్ద గరిష్ట కుప్ప ఉండదు. మిన్ హీప్, మరోవైపు, విలువలో పెరుగుతున్న వరుస నోడ్‌లతో చిన్న విలువగా రూట్‌తో వ్యతిరేకం; ప్రతి చైల్డ్ నోడ్ దాని పేరెంట్ కంటే ఎక్కువ లేదా సమానమైన విలువను కలిగి ఉంటుంది. ఇది కూడా పూర్తి బైనరీ చెట్టు. గరిష్ట కుప్పకు ఉదాహరణ:
గరిష్ట కుప్పను శ్రేణి నుండి నిర్మించవచ్చు. ఈ శ్రేణి చెట్టు పరంగా ఆలోచించబడుతుంది. ఒక కుప్ప కోసం, మూలం, (చెట్టు యొక్క టాప్ పేరెంట్ నోడ్) స్థానం (సూచిక) n వద్ద నిల్వ చేయబడితే, అది అర్రే, theArray కోసం , theArray[n] గా నిర్వచించబడుతుంది.. ఎడమ మరియు కుడి-చైల్డ్ నోడ్‌లు వరుసగా శ్రేణి [2n+1] మరియు అర్రే[2n+2] వద్ద ఉంటాయి . గరిష్ట హీప్ కోసం, రూట్ theArray[0] వద్ద ఉంది . స్థాయి n కోసం, రూట్ n = 0: theArr[n] అనేది పేరెంట్ నోడ్ దిArr[(2*n)+1] అనేది ఎడమ చైల్డ్ నోడ్ దిArr[(2*n)+2] అనేది కుడి చైల్డ్ నోడ్.
ప్రయారిటీ క్యూ క్లాస్
జావాలోని హీప్స్‌ని ప్రయారిటీ క్యూ క్లాస్‌ని ఉపయోగించి అమలు చేయవచ్చు . సేకరణలో అత్యంత లేదా అతి తక్కువ ముఖ్యమైన అంశాన్ని కనుగొనడానికి ప్రాధాన్యత క్యూలు ఉపయోగించబడతాయి.జావా .util.package లో PriorityQueue తరగతిని కనుగొనవచ్చు . ప్రాధాన్యత క్యూలు తప్పనిసరిగా పోల్చదగిన వస్తువులతో ఏర్పడాలి, తద్వారా అవి క్యూలో ఒక నిర్దిష్ట క్రమంలో ఉంచబడతాయి. PriorityQueue ఒక కంపారిటర్‌ని కలిగి ఉంటుంది, తద్వారా వస్తువుల మధ్య పోలిక చేయబడుతుంది మరియు ఈ పోలిక ప్రకారం క్యూ ఏర్పడుతుంది. ఒక ఉదాహరణ: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());
}
}
}
1 3 6 7 11
ఈ ఉదాహరణలో, intQueue యొక్క డిఫాల్ట్ పరిమాణం 11, కాబట్టి పేర్కొనబడలేదు (సాధారణంగా కంపారిటర్ ముందు మొదటి వాదన) మరియు కంపారిటర్ ఇలా ఇవ్వబడింది:
(a,b) -> a - b
ఇది intQueue లోని అంశాల మధ్య పోలికను చేస్తుంది మరియు దానిని ఆరోహణ క్రమంలో శ్రేణి పొడవులుగా క్రమబద్ధీకరిస్తుంది.
మ్యాక్స్ హీప్‌ని సృష్టించడానికి ప్రాధాన్యత క్యూ అమలు
PriorityQueue క్లాస్ కంపారిటర్ లేకుండా మిని హీప్‌కి డిఫాల్ట్ అవుతుంది . మిన్ హీప్ అనేది మాక్స్ హీప్‌కి వ్యతిరేకం కాబట్టి రూట్ అనేది అతి చిన్న విలువ మరియు వరుస చైల్డ్ నోడ్‌లు రూట్ మరియు తదుపరి పేరెంటల్ నోడ్‌లకు పెద్దవి లేదా సమానంగా ఉంటాయి. ఈ కారణంగా, మాక్స్ హీప్ కోసం, జావా కలెక్షన్స్ ఫ్రేమ్‌వర్క్ నుండి రివర్స్ ఆర్డర్()ని కంపారిటర్‌గా ఉపయోగించడం అవసరం . ఇది నిమి హీప్ కాకుండా గరిష్ట స్థాయిని పొందేలా చేస్తుంది. ఈ తరగతిలో add() , కలిగి() , తొలగించు() , పోల్() , మరియు పీక్() వంటి ఉపయోగకరమైన పద్ధతులు ఉన్నాయి .| పద్ధతి | వివరణ | సమయం సంక్లిష్టత |
|---|---|---|
| జోడించు(J) | చెట్టు చివర మూలకం J జోడిస్తుంది | O(LogN) |
| తొలగించు(J) | చెట్టు నుండి J విలువను తీసివేయండి | పై) |
| ఎన్నికలో() | చెట్టు యొక్క గరిష్ట మూలకాన్ని తొలగిస్తుంది | O(LogN) |
| పీక్() | చెట్టు పైభాగంలో ఉన్న మూల మూలకాన్ని అందిస్తుంది | O(1) |
| కలిగి (J) | J క్యూలో ఉంటే ఒప్పు, కాకపోతే తప్పు అని చూపుతుంది | పై) |
జావాలో మాక్స్ హీప్ (మాక్స్‌హీప్) ఎలా సృష్టించబడుతుందో క్రింది కోడ్ ఉదాహరణ. చేయవలసిన మొదటి విషయం ఏమిటంటే, గరిష్ట హీప్ సృష్టించబడే విలువలతో శ్రేణిని పూరించడం. దీనిని అర్రే అంటారు . తరువాత, ఒక PriorityQueue , theQueue సృష్టించబడుతుంది మరియు ఆపై theArray నుండి మూలకాలు దీనికి జోడించబడతాయి. ఇది క్యూ చివరిలో 10ని జోడించడానికి add() , ఉదా. theQueue.add(10) పద్ధతిని ఉపయోగిస్తుంది . PriorityQueue క్లాస్ యొక్క కొన్ని కార్యాచరణలను వివరించడానికి , మెథడ్ పీక్() కుప్ప యొక్క తలని కనుగొనడానికి ఉపయోగించబడుతుంది మరియు ఇది గరిష్ట విలువ, ఈ సందర్భంలో, 99. కుప్ప పరిమాణాన్ని తనిఖీ చేయడం తదుపరి పని. పరిమాణం () ఉపయోగించిఇది 9గా కనుగొనబడింది మరియు ఇది కన్సోల్‌కు ముద్రించబడుతుంది. విధానం రైట్‌మాక్స్‌హీప్ క్యూలోని మూలకాలను రూట్‌లో, ఎడమ-పిల్లలు రూట్‌తో తల్లిదండ్రులుగా, కుడి-పిల్లలు తల్లిదండ్రులుగా, కుడి-పిల్లలు తల్లిదండ్రులుగా, ఎడమ-పిల్లలు మొదటి ఎడమ-పిల్లతో తల్లితండ్రులుగా, కుడి-పిల్లలు మొదటి ఎడమ-పిల్లతో ఇలా వ్రాస్తారు. తల్లిదండ్రులు, కుడి-పిల్లలు మొదటి కుడి-పిల్లలు తల్లిదండ్రులు, ఎడమ-పిల్లలు మొదటి కుడి-పిల్ల తల్లిదండ్రులు మొదలైనవి, తరువాతి విలువలతో ఎడమ మరియు కుడి పిల్లలను తల్లిదండ్రులుగా పైన పేర్కొన్న క్రమంలో ఉపయోగిస్తున్నారు.
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);
}
}
99 క్యూ పరిమాణం? 9 లూప్ 99 51 19 13 10 5 కోసం ఉపయోగించి వ్రాసిన క్యూ 6 3 9 క్యూలో 10 ఉందా? పోల్() 99 51 19 13 9 ఉపయోగించి నిజమైన క్యూ వ్రాయబడింది 6 5 3 క్యూ పరిమాణం? 0
గరిష్ట Heapify
బైనరీ ట్రీ గరిష్ట కుప్ప అని నిర్ధారించడానికి Max Heapify అల్గోరిథం ఉపయోగించబడుతుంది. మనం నోడ్, n మరియు దాని చైల్డ్ నోడ్‌ల వద్ద ఉంటే, ఎడమ మరియు కుడి కూడా గరిష్టంగా కుప్పలుగా ఉంటే, అప్పుడు గొప్పది, మనకు గరిష్ట కుప్ప ఉంటుంది. చెట్టు అంతటా ఇది కాకపోతే, మనకు గరిష్ట కుప్ప లేదు. Max Heapify అల్గోరిథం చెట్టును క్రమబద్ధీకరించడానికి ఉపయోగించబడుతుంది, తద్వారా అది మాక్స్‌హీప్ సూత్రాలకు కట్టుబడి ఉంటుంది. Max Heapify ఒక నోడ్‌లో మాత్రమే పని చేస్తుంది. శ్రేణి గరిష్ట కుప్ప శ్రేణిగా ఉండాల్సిన అవసరం ఉంటే, అప్పుడు అన్ని ఉప వృక్షాలను తప్పనిసరిగా రూట్‌కు ముందు మాక్స్‌హీప్‌గా మార్చాలి. ప్రతి నోడ్‌లో అల్గోరిథం తప్పనిసరిగా ఉపయోగించబడాలి. ఇది N/2 నోడ్‌లపై చేయబడుతుంది (ఆకులు గరిష్టంగా కుప్ప అవసరాలకు కట్టుబడి ఉంటాయి). కుప్ప యొక్క సమయ సంక్లిష్టత O(NlogN), మరియు ఎత్తు X వద్ద ఒక నోడ్‌కు, సమయ సంక్లిష్టత O(X). కింది కోడ్ చెట్టును (ఒక శ్రేణి) ఎలా గరిష్టీకరించాలో చూపుతుంది.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();
}
}
}
కొత్తఅరే:99 51 19 10 3 13 65 9 రూట్ : 99 పేరెంట్ నోడ్ : 99 ఎడమ చైల్డ్ : 51 కుడి బిడ్డ :19 పేరెంట్ నోడ్ : 51 ఎడమ చైల్డ్ : 10 కుడి చైల్డ్ :3 పేరెంట్ నోడ్ : 19 ఎడమ చైల్డ్ : 13 కుడి చైల్డ్ :6 పేరెంట్ నోడ్ : 10 ఎడమ చైల్డ్ : 5 కుడి బిడ్డ : 999999999 పేరెంట్ నోడ్ : 99 లెఫ్ట్ చైల్డ్ : 51 రైట్ చైల్డ్ :19 పేరెంట్ నోడ్ : 51 లెఫ్ట్ చైల్డ్ : 10 రైట్ చైల్డ్ :3 పేరెంట్ నోడ్ : 19 లెఫ్ట్ చైల్డ్ : 13 రైట్ చైల్డ్ :6 పేరెంట్ నోడ్ : 10 లెఫ్ట్ చైల్డ్ : 5 రైట్ చైల్డ్ :999 పేరెంట్ నోడ్ : 99 లెఫ్ట్ చైల్డ్ : 51 రైట్ చైల్డ్ :19 పేరెంట్ నోడ్ : 51 లెఫ్ట్ చైల్డ్ : 10 రైట్ చైల్డ్ :3 పేరెంట్ నోడ్ : 19 లెఫ్ట్ చైల్డ్ : 13 రైట్ చైల్డ్ :6 పేరెంట్ నోడ్ : 10 లెఫ్ట్ చైల్డ్ : 5 రైట్ చైల్డ్ :96 పేరెంట్ నోడ్ : 10 ఎడమ బిడ్డ : 5 కుడి బిడ్డ :96 పేరెంట్ నోడ్ : 10 ఎడమ బిడ్డ : 5 కుడి బిడ్డ :9
