A max-hoop is een volledige binaire boom waarin de waarde in elk intern knooppunt groter is dan of gelijk is aan de waarden in de kinderen van dat knooppunt. Het in kaart brengen van de elementen van een heap in een array is triviaal: als een knooppunt een index k heeft, dan wordt het linkerkind opgeslagen op index 2k + 1 en het rechterkind op index 2k + 2.
Illustratie: Max Hoop
verschil tussen array en arraylist
Hoe wordt Max Heap vertegenwoordigd?
A-Max Heap is een complete binaire boom. A-Max-heap wordt doorgaans weergegeven als een array. Het rootelement bevindt zich op Arr[0]. Onderstaande tabel toont indexen van andere knooppunten voor de it knooppunt, dat wil zeggen Arr[i]:
Arr[(i-1)/2] Geeft het bovenliggende knooppunt terug.
Arr[(2*i)+1] Geeft het linker onderliggende knooppunt terug.
Arr[(2*i)+2] Geeft het rechter onderliggende knooppunt terug.
De bewerkingen op Max Heap zijn als volgt:
- getMax(): Het retourneert het rootelement van Max Heap. De tijdscomplexiteit van deze operatie is O(1) .
- extraheerMax(): Verwijdert het maximale element uit MaxHeap . De tijdscomplexiteit van deze operatie is O(Logboek n) aangezien deze bewerking de heap-eigenschap moet behouden door de heapify() methode na het verwijderen van de wortel.
- invoegen(): Het plaatsen van een nieuwe sleutel duurt O(Logboek n) tijd. We voegen een nieuwe sleutel toe aan het einde van de boom. Als de nieuwe sleutel kleiner is dan de bovenliggende sleutel, hoeven we niets te doen. Anders moeten we omhoog gaan om de geschonden heap-eigenschap te repareren.
Opmerking: In de onderstaande implementatie indexeren we vanaf index 1 om de implementatie te vereenvoudigen.
Methoden:
Er zijn 2 methoden waarmee we het genoemde doel kunnen bereiken:
- Basisaanpak door te creëren maxHeapify() methode
- Gebruik makend van Collecties.reverseOrder() methode via bibliotheekfuncties
Methode 1: Basisaanpak door te creëren maxHeapify() methode
We zullen een methode maken, ervan uitgaande dat de linker en rechter subboom al zijn opgestapeld, we hoeven alleen de root te repareren.
aw java
Voorbeeld
Java
// 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>(grootte />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(leftChild(pos)); } anders { swap(pos, rightChild(pos)); maxHeapify(rightChild(pos)); } } } // Methode 7 // Voegt een nieuw element in in de maximale heap public void insert(int element) { Heap[size] = element; // Ga naar boven en repareer de geschonden eigenschap int current = size; while (Heap[huidig]> Heap[ouder(huidig)]) { swap(huidig, ouder(huidig)); huidig = ouder(huidig); } maat++; } // Methode 8 // Heap public void print() weergeven { for (int i = 0; i 2; i++) { System.out.print('Parent Node: ' + Heap[i]); if (leftChild(i) // als het kind zich buiten de grens bevindt // van de array System.out.print(' Left Child Node: ' + Heap[leftChild(i)]); if (rightChild(i ) // de rechter onderliggende index mag niet // buiten de index van de array System.out.print(' Right Child Node: ' + Heap[rightChild(i)]); ; // voor nieuwe regel } } // Methode 9 // Verwijder een element uit max heap public int extractMax() { int popped = Heap[0] = Heap[--size]; ; return popped; } // Methode 10 // hoofdstuurprogrammamethode public static void main(String[] arg) {// Toon bericht voor betere leesbaarheid System.out.println('De maximale heap is '); = nieuwe MaxHeap(15); // Knooppunten invoegen // Aangepaste invoer maxHeap.insert(5); maxHeap.insert(17); maxHeap.insert(19); maxHeap.insert(6); maxHeap.insert(22); maxHeap.insert(9); // MaxHeap() aanroepen zoals hierboven gedefinieerd maxHeap.print(); waarde in heap System.out.println('De maximale waarde is ' + maxHeap.extractMax()); } }> |
mijnlivericket
>
c-codearray van tekenreeksen
>Uitvoer
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>
Methode 2: De methode Collections.reverseOrder() gebruiken via bibliotheekfuncties
We gebruiken de klasse PriorityQueue om Heaps in Java te implementeren. Standaard wordt Min Heap door deze klasse geïmplementeerd. Om Max Heap te implementeren, gebruiken we de Collections.reverseOrder() -methode.
Voorbeeld
Java
// 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()); } }> |
>
Java-standaardparameters
>Uitvoer
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>