A Max-Heap ist ein vollständiger Binärbaum, in dem der Wert in jedem internen Knoten größer oder gleich den Werten in den untergeordneten Knoten dieses Knotens ist. Die Zuordnung der Elemente eines Heaps in ein Array ist trivial: Wenn ein Knoten mit einem Index k gespeichert wird, wird sein linkes untergeordnetes Element bei Index 2k + 1 und sein rechtes untergeordnetes Element bei Index 2k + 2 gespeichert.
Illustration: Max Heap
Wie wird Max Heap dargestellt?
A-Max Heap ist ein vollständiger Binärbaum. A-Max-Heap wird normalerweise als Array dargestellt. Das Wurzelelement befindet sich bei Arr[0]. Die folgende Tabelle zeigt Indizes anderer Knoten für ith Knoten, d. h. Arr[i]:
Arr[(i-1)/2] Gibt den übergeordneten Knoten zurück.
Arr[(2*i)+1] Gibt den linken untergeordneten Knoten zurück.
Arr[(2*i)+2] Gibt den rechten untergeordneten Knoten zurück.Alphabet als Zahlen
Die Operationen auf Max Heap sind wie folgt:
- getMax(): Es gibt das Wurzelelement von Max Heap zurück. Die zeitliche Komplexität dieser Operation beträgt O(1) .
- extractMax(): Entfernt das maximale Element aus MaxHeap . Die zeitliche Komplexität dieser Operation beträgt O(Log n) da dieser Vorgang die Heap-Eigenschaft durch den Aufruf von beibehalten muss heapify()-Methode nach dem Entfernen der Wurzel.
- einfügen(): Das Einsetzen eines neuen Schlüssels dauert O(Log n) Zeit. Wir fügen am Ende des Baums einen neuen Schlüssel hinzu. Wenn der neue Schlüssel kleiner als sein übergeordneter Schlüssel ist, müssen wir nichts tun. Andernfalls müssen wir nach oben gehen, um die verletzte Heap-Eigenschaft zu beheben.
Notiz: In der folgenden Implementierung führen wir die Indizierung ab Index 1 durch, um die Implementierung zu vereinfachen.
Methoden:
Es gibt zwei Methoden, mit denen wir das aufgeführte Ziel erreichen können:
- Grundlegender Ansatz durch Erstellen maxHeapify() Methode
- Benutzen Collections.reverseOrder() Methode über Bibliotheksfunktionen
Methode 1: Grundlegender Ansatz durch Erstellen maxHeapify() Methode
Wir werden eine Methode erstellen, die davon ausgeht, dass der linke und der rechte Teilbaum bereits gehäuft sind. Wir müssen nur die Wurzel reparieren.
Beispiel
Java
Java vergleicht Zeichenfolgen
// 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>(Größe />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)); } else { swap(pos, rightChild(pos)); maxHeapify(rightChild(pos)); } } } // Methode 7 // Fügt ein neues Element in den maximalen Heap ein public void insert(int element) { Heap[size] = element; // Nach oben durchlaufen und verletzte Eigenschaft beheben int current = size; while (Heap[current]> Heap[parent(current)]) { swap(current, parent(current)); current = parent(current); } size++; } // Methode 8 // Heap anzeigen public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node : ' + Heap[i]); if (leftChild(i) // wenn das Kind außerhalb der Grenze // des Arrays liegt System.out.print(' Left Child Node: ' + Heap[leftChild(i)]); if (rightChild(i ) // der rechte untergeordnete Index darf nicht // außerhalb des Index des Arrays liegen System.out.print(' Right Child Node: ' + Heap[rightChild(i)]); ; // für neue Zeile } } // Methode 9 // Ein Element aus dem Max-Heap entfernen public int extractMax() { int popped = Heap[0] = Heap[--size]; ; return popped; } // Methode 10 // Haupttreibermethode public static void main(String[] arg) { // Meldung zur besseren Lesbarkeit anzeigen System.out.println('The MaxHeap maxHeap.' = new MaxHeap(15); // Einfügen von Knoten // Benutzerdefinierte Eingaben maxHeap.insert(17); maxHeap.insert(19); maxHeap.insert(22); // Aufruf von maxHeap() wie oben definiert maxHeap.print(); Wert im Heap System.out.println('Der maximale Wert ist ' + maxHeap.extractMax()); } }> |
>
>
string.replaceall in JavaAusgabe
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: Verwendung der Methode Collections.reverseOrder() über Bibliotheksfunktionen
Wir verwenden die PriorityQueue-Klasse, um Heaps in Java zu implementieren. Standardmäßig wird Min Heap von dieser Klasse implementiert. Um Max Heap zu implementieren, verwenden wir die Methode Collections.reverseOrder().
Beispiel
Java
bfs und dfs
// 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()); } }> |
>
>Ausgabe
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>