Implementieren von Min-Max-Heap in Java

1. Einführung in Min-Max-Heap in Java
2. Max-Heap mit der Klasse PriorityQueue und Collections.reverseOrder() in Java implementieren
3. Implementierung von Min-Heap mit der Klasse PriorityQueue in Java

Dieser Artikel implementiert einen Max-Heap und einen Min-Heap mit der Klasse PriorityQueue. Wir werden auch das Einfügen und Löschen der Elemente aus dem Heap demonstrieren.

Einführung in Min-Max-Heap in Java

Ein Heap ist eine auf Bäumen basierende Datenstruktur, die einen vollständigen Binärbaum bildet. Heaps werden als Array dargestellt. Es gibt zwei Arten von Heaps, und zwar Minimum Heap und Maximum Heap. Der minimale Heap, auch als Min-Heap bekannt, hat den kleinsten Wert in seinem Wurzelknoten oder dem übergeordneten Knoten. In ähnlicher Weise hat der max-heap den größten Wert im Root-Knoten oder im Eltern-Knoten. Daher erleichtert die Heap-Datenstruktur das Extrahieren des größten und kleinsten Elements aus einem Array. Wir können das größte und das kleinste Element in O(1) erhalten. Die Komplexität zum Entfernen oder Einfügen der Elemente in und aus dem Heap beträgt O(log N).

Ein Min-Max-Heap ist eine Datenstruktur, die abwechselnd minimale und maximale Ebenen enthält. Der Wurzelknoten enthält den kleinsten Wert, und die nächste Ebene darunter repräsentiert den größten Wert. Die Minimalwerte werden mit geraden Werten wie 0, 2, 4 dargestellt. Die ungeraden Werte wie 1, 3, 5 repräsentieren die Maximalwerte.

Max-Heap mit der Klasse PriorityQueue und Collections.reverseOrder() in Java implementieren

Wir können die Klasse PriorityQueue verwenden, um die Heaps in Java zu implementieren. Die Klasse implementiert standardmäßig den Min-Heap, und wir können die Methode reverseOrder() von Collections verwenden, um den Max-Heap zu implementieren. Wir können die Methode peek() verwenden, um das Element aus dem Wurzelknoten in einem Heap anzuzeigen. Die Methode poll() gibt den Wert am Wurzelknoten zurück und entfernt ihn. Wir können die Methode contains() verwenden, um zu überprüfen, ob ein Element in einem Heap vorhanden ist.

Importieren Sie beispielsweise alles aus dem Paket java.util. Erstellen Sie eine Klasse MaxHeap und schreiben Sie die Hauptmethode. Erstellen Sie dann eine Instanz der Klasse PriorityQueue als pq. Verwenden Sie den generischen Typ, um die Instanz Integer zu erstellen. Schreiben Sie Collections.reverseOrder() in die Klammer, während Sie das Objekt erstellen. Verwenden Sie die Methode add(), um vier ganzzahlige Werte hinzuzufügen. Rufen Sie die Methode peek() mit dem Objekt pq auf und drucken Sie sie aus. Verwenden Sie dann die Methode poll() für das Objekt. Als nächstes rufen Sie die Methode remove() mit dem Wert 30 als Parameter auf und geben dann die Elemente im Array mit den Methoden iterator() und hasNext() aus. Schließlich verwenden Sie die Methode contains() mit einem Parameter 20.

Im unten stehenden Beispiel importiert import java.util.* die Klasse PriorityQueue, mit der wir einen Max-Heap erstellt haben. Wir haben dem Heap die Werte 1, 2, 3 und 4 hinzugefügt. Die Methode peek() hat den Wert 4 zurückgegeben, der der grösste in einem Heap ist. Dann entfernte die Methode poll() die maximale Zahl 4. Dann haben wir mit der Methode remove() die Zahl 3 entfernt und die restlichen Elemente in einem Heap ausgegeben. Es hat die Werte 1 und 2 gedruckt, da wir bereits 3 und 4 entfernt haben. Schließlich haben wir mit der Methode contains() überprüft, ob der Heap eine Zahl 2 enthält. Es gab true zurück, da die Zahl in einem Haufen existiert. Daher haben wir den max-heap mit der Klasse PriorityQueue unter Verwendung von Collectios.reverseOrder() implementiert.

Beispielcode:

import java.util.*;

class MaxHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr3.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(2);
    System.out.println("Does the heap contains 2 ?" + b);
  }
}

Ausgabe:

The highest value in the heap:4
after removing 3:
2
1
Does the heap contains 2 ?true

Implementierung von Min-Heap mit der Klasse PriorityQueue in Java

Die Klasse PriorityQueue implementiert standardmäßig min Heap. Wir wenden dieselbe Implementierungsmethode für den Min-Heap an wie für den Max-Heap. Wir verwenden dieselben Methoden wie peek(), remove(), poll() und contains(), um dieselben Operationen durchzuführen.

Im folgenden Beispiel haben wir die Zahlen 1, 2, 3 und 4 in einem Haufen hinzugefügt. Die Methode peek() hat das Element im Wurzelknoten zurückgegeben, das, wie in der Ausgabe gezeigt, 1 ist. Wir haben die Methode poll() verwendet, um das Wurzelknotenelement 1 zu entfernen. Den Wert 3 haben wir mit der Funktion remove() wieder aus dem Heap entfernt. Nach dem Entfernen dieser Werte enthält unser Heap nur noch die Elemente 2 und 4. Schließlich haben wir die Methode contains() verwendet, um zu überprüfen, ob wir in einem Heap den Wert 3 haben. Da wir es bereits entfernt haben, gibt die Methode einen false Wert zurück. Daher haben wir mit der Klasse PriorityQueue einen Min-Heap implementiert.

Beispielcode:

import java.util.*;

class MinHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(3);
    System.out.println("Does the heap contains 3 ?" + b);
  }
}

Ausgabe:

The highest value in the heap:1
after removing 3:
2
4
Does the heap contains 2 ?false