EN maks-haug er et komplett binært tre der verdien i hver intern node er større enn eller lik verdiene i barna til den noden. Å kartlegge elementene i en haug til en matrise er trivielt: hvis en node er lagret en indeks k, lagres dens venstre underordnede ved indeks 2k + 1 og dets høyre underordnede ved indeks 2k + 2.
Illustrasjon: Max Heap
Hvordan er Max Heap representert?
A-Max Heap er et komplett binært tre. A-Max-haug er vanligvis representert som en matrise. Rotelementet vil være ved Arr[0]. Tabellen nedenfor viser indekser for andre noder for ith node, dvs. Arr[i]:
Arr[(i-1)/2] Returnerer overordnet node.
Arr[(2*i)+1] Returnerer venstre underordnet node.
Arr[(2*i)+2] Returnerer høyre underordnet node.
Operasjoner på Max Heap er som følger:
- getMax(): Den returnerer rotelementet til Max Heap. Tidskompleksiteten til denne operasjonen er O(1) .
- extractMax(): Fjerner det maksimale elementet fra MaxHeap . Tidskompleksiteten til denne operasjonen er O(Logg n) ettersom denne operasjonen må opprettholde heap-egenskapen ved å ringe til heapify() metode etter å ha fjernet roten.
- sett inn(): Å sette inn en ny nøkkel tar O(Logg n) tid. Vi legger til en ny nøkkel i enden av treet. Hvis den nye nøkkelen er mindre enn overordnet, trenger vi ikke å gjøre noe. Ellers må vi krysse opp for å fikse den krenkede haugeiendommen.
Merk: I implementeringen nedenfor gjør vi indeksering fra indeks 1 for å forenkle implementeringen.
ipconfig på Ubuntu
Metoder:
Det er 2 metoder for å nå målet som er oppført:
- Grunnleggende tilnærming ved å skape maxHeapify() metode
- Ved hjelp av Collections.reverseOrder() metode via bibliotekfunksjoner
Metode 1: Grunnleggende tilnærming ved å skape maxHeapify() metode
Vi vil lage en metode forutsatt at venstre og høyre undertre allerede er heapified, vi trenger bare å fikse roten.
Eksempel
Java
java-strengsammenkobling
// Java program to implement Max Heap> // Main class> public> class> MaxHeap {> >private> int>[] Heap;> >private> int> size;> >private> int> maxsize;> >// Constructor to initialize an> >// empty max heap with given maximum> >// capacity> >public> MaxHeap(>int> maxsize)> >{> >// This keyword refers to current instance itself> >this>.maxsize = maxsize;> >this>.size =>0>;> >Heap =>new> int>[>this>.maxsize];> >}> >// Method 1> >// Returning position of parent> >private> int> parent(>int> pos) {>return> (pos ->1>) />2>; }> >// Method 2> >// Returning left children> >private> int> leftChild(>int> pos) {>return> (>2> * pos) +>1>; }> >// Method 3> >// Returning right children> >private> int> rightChild(>int> pos)> >{> >return> (>2> * pos) +>2>;> >}> >// Method 4> >// Returning true if given node is leaf> >private> boolean> isLeaf(>int> pos)> >{> >if> (pos>(størrelse />2>) && pos <= size) {> >return> true>;> >}> >return> false>;> >}> >// Method 5> >// Swapping nodes> >private> void> swap(>int> fpos,>int> spos)> >{> >int> tmp;> >tmp = Heap[fpos];> >Heap[fpos] = Heap[spos];> >Heap[spos] = tmp;> >}> >// Method 6> >// Recursive function to max heapify given subtree> >private> void> maxHeapify(>int> pos)> >{> >if> (isLeaf(pos))> >return>;> >if> (Heap[pos] || Heap[pos] if (Heap[leftChild(pos)]>Heap[rightChild(pos)]) { swap(pos, leftChild(pos)); maxHeapify(venstrebarn(pos)); } annet { swap(pos, rightChild(pos)); maxHeapify(rightChild(pos)); } } } // Metode 7 // Setter inn et nytt element til max heap public void insert(int element) { Heap[size] = element; // Traverse opp og fikse krenket egenskap int strøm = størrelse; while (Heap[current]> Heap[parent(current)]) { swap(current, parent(current)); gjeldende = forelder(strøm); } størrelse++; } // Metode 8 // For å vise heap public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node : ' + Heap[i]); if (venstreBarn(i) // hvis barnet er utenfor grensen // av matrisen System.out.print(' Venstre Child-node: ' + Heap[venstreBarn(i)]); if (høyreBarn(i) ) // den høyre underordnede indeksen må ikke // være utenfor indeksen til arrayen System.out.print(' Høyre underordnet node: ' + Heap[rightChild(i)]); ; // for ny linje } } // Metode 9 // Fjern et element fra max heap public int extractMax() { int popped = Heap[0] = maxHeapify(0) ; return popped; } // Metode 10 // hoveddrivermetode public static void main(String[] arg) { // Vis melding for bedre lesbarhet System.out.println('MaxHeap maxHeap = new MaxHeap(15); // Setter inn noder maxHeap.insert(3) maxHeap.insert(10); maxHeap.insert(19); maxHeap.insert(22); verdi i heap System.out.println('Maksverdien er ' + maxHeap.extractMax()); } }> |
>
>Produksjon
The Max Heap is Parent Node : 84 Left Child Node: 22 Right Child Node: 19 Parent Node : 22 Left Child Node: 17 Right Child Node: 10 Parent Node : 19 Left Child Node: 5 Right Child Node: 6 Parent Node : 17 Left Child Node: 3 Right Child Node: 9 The max val is 84>
Metode 2: Bruke Collections.reverseOrder()-metoden via bibliotekfunksjoner
Vi bruker PriorityQueue-klassen for å implementere Heaps i Java. Som standard er Min Heap implementert av denne klassen. For å implementere Max Heap bruker vi Collections.reverseOrder() metoden.
Eksempel
Java
123 film
// Java program to demonstrate working> // of PriorityQueue as a Max Heap> // Using Collections.reverseOrder() method> // Importing all utility classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue> >=>new> PriorityQueue(> >Collections.reverseOrder());> >// Adding items to our priority queue> >// using add() method> >pQueue.add(>10>);> >pQueue.add(>30>);> >pQueue.add(>20>);> >pQueue.add(>400>);> >// Printing the most priority element> >System.out.println(>'Head value using peek function:'> >+ pQueue.peek());> >// Printing all elements> >System.out.println(>'The queue elements:'>);> >Iterator itr = pQueue.iterator();> >while> (itr.hasNext())> >System.out.println(itr.next());> >// Removing the top priority element (or head) and> >// printing the modified pQueue using poll()> >pQueue.poll();> >System.out.println(>'After removing an element '> >+>'with poll function:'>);> >Iterator itr2 = pQueue.iterator();> >while> (itr2.hasNext())> >System.out.println(itr2.next());> >// Removing 30 using remove() method> >pQueue.remove(>30>);> >System.out.println(>'after removing 30 with'> >+>' remove function:'>);> >Iterator itr3 = pQueue.iterator();> >while> (itr3.hasNext())> >System.out.println(itr3.next());> >// Check if an element is present using contains()> >boolean> b = pQueue.contains(>20>);> >System.out.println(>'Priority queue contains 20 '> >+>'or not?: '> + b);> >// Getting objects from the queue using toArray()> >// in an array and print the array> >Object[] arr = pQueue.toArray();> >System.out.println(>'Value in array: '>);> >for> (>int> i =>0>; i System.out.println('Value: ' + arr[i].toString()); } }> |
>
>Produksjon
Head value using peek function:400 The queue elements: 400 30 20 10 After removing an element with poll function: 30 10 20 after removing 30 with remove function: 20 10 Priority queue contains 20 or not?: true Value in array: Value: 20 Value: 10>