Min-Heap in Java implementieren

1. Implementierung von Min Heap ohne Verwendung der Bibliothek in Java
2. Implementierung von Min-Heap mit PriorityQueue in Java

Ein Min Heap ist ein Heap, bei dem jeder interne Knoten kleiner oder gleich den Werten seiner untergeordneten Elemente ist. Wir werden in den folgenden Punkten sehen, wie Sie Min Heap mit und ohne Verwendung einer Bibliothek implementieren.

Implementierung von Min Heap ohne Verwendung der Bibliothek in Java

In diesem Beispiel sehen wir die Implementierung ohne Verwendung einer Bibliothek. Hier erstellen wir eine Klasse JavaMinHeap, in der wir drei Instanzvariablen erstellen. HeapArray ist ein Array vom Typ int, das alle Werte des Heaps behält, size ist die Größe des Heaps, maxSize speichert die maximale Größe des HeapArray. Außerdem erstellen wir eine statische Variable FRONT vom Typ int und initialisieren diese mit 1.

Wir bekommen maxSize als Parameter im Konstruktor und speichern ihn in der Instanzvariablen maxSize. Wir initialisieren size mit 0 und HeapArray mit einem Array von int mit der Grösse maxSize + 1. Wir speichern den Mindestwert von Integer am ersten Index von HeapArray.

Jetzt erstellen wir Methoden zum Ausführen von Operationen auf dem Heap. Die Funktion parent() nimmt eine position als Parameter und gibt das Elternelement der übergebenen Position des Knotens zurück. Dann erstellen wir leftChild(), das das linke Kind der empfangenen Position als Parameter zurückgibt. Das gleiche gilt für das rechte Kind, das rightChild() verwendet, das den Wert des Knotens (2 * position) + 1 zurückgibt.

isLeaf() prüft, ob ein Knoten ein Blattknoten ist oder nicht, was bedeutet, dass er ein Kind hat. swapNodes() ist eine Methode, die den Wert der Position fpos des Knotens mit der Position spos tauscht. In der Methode erstellen wir eine temp Variable und initialisieren sie, die fpos Position von HeapArray und speichern den spos Wert von HeapArray in HeapArray[fpos]. Nun speichern wir den temp Wert in HeapArray[spos].

convertToMinHeap() prüft, ob die als Parameter empfangene Position ein Blatt ist oder nicht mit isLeaf und wenn nicht, dann prüft, ob der aktuelle Wert an der Position von HeapArray größer ist als das linke Kind oder das rechte Kind. Dann prüfen wir, ob das linke Kind kleiner ist als das rechte Kind, und wenn ja, verwenden wir swapNodes() um die Knoten zu tauschen und übergeben das position und das linke Kind an position. Wir konvertieren das empfangene linke Kind erneut mit convertToMinHeap() in einen min-Heap.

Wir verwenden insert(), um die Werte in den Min-Heap einzufügen. In insert() kehren wir ohne Einfügen zurück, wenn das Array maxSize erreicht hat; wenn nicht, erhalten wir die Position bei ++size und fügen das empfangene Element bei HeapArray[++size] ein. Wir setzen size auf current. Wir erstellen eine Schleife und tauschen Knoten aus, wenn das Element an der current Position kleiner als sein Elternteil ist.

Um den Min-Heap zu drucken, erstellen wir printheap() und durchlaufen das HeapArray, wobei sich das Elternteil an der ith-Position befindet, das linke Kind an der 2 * i Position und das rechte Kind ist an der Position 2 * i + 1. In der Funktion main() verwenden wir insert(), um Elemente in den Heap einzufügen.

public class JavaMinHeap {
  private final int[] HeapArray;
  private int size;
  private final int maxsize;

  private static final int FRONT = 1;

  public JavaMinHeap(int maxsize) {
    this.maxsize = maxsize;
    this.size = 0;
    HeapArray = new int[this.maxsize + 1];
    HeapArray[0] = Integer.MIN_VALUE;
  }

  private int parent(int position) {
    return position / 2;
  }

  private int leftChild(int position) {
    return (2 * position);
  }

  private int rightChild(int position) {
    return (2 * position) + 1;
  }

  private boolean isLeaf(int position) {
    if (position >= (size / 2) && position <= size) {
      return true;
    }
    return false;
  }

  private void swapNodes(int fpos, int spos) {
    int temp;
    temp = HeapArray[fpos];
    HeapArray[fpos] = HeapArray[spos];
    HeapArray[spos] = temp;
  }

  private void convertToMinHeap(int position) {
    if (!isLeaf(position)) {
      if (HeapArray[position] > HeapArray[leftChild(position)]
          || HeapArray[position] > HeapArray[rightChild(position)]) {
        if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
          swapNodes(position, leftChild(position));
          convertToMinHeap(leftChild(position));
        } else {
          swapNodes(position, rightChild(position));
          convertToMinHeap(rightChild(position));
        }
      }
    }
  }

  public void insert(int element) {
    if (size >= maxsize) {
      return;
    }
    HeapArray[++size] = element;
    int current = size;

    while (HeapArray[current] < HeapArray[parent(current)]) {
      swapNodes(current, parent(current));
      current = parent(current);
    }
  }

  public void printHeap() {
    for (int i = 1; i <= size / 2; i++) {
      System.out.println("PARENT : " + HeapArray[i]);

      System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);

      System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
      System.out.println();
    }
  }

  public static void main(String[] arg) {
    System.out.println("The Min Heap is ");
    JavaMinHeap minHeap = new JavaMinHeap(10);
    minHeap.insert(10);
    minHeap.insert(2);
    minHeap.insert(7);
    minHeap.insert(15);
    minHeap.insert(90);
    minHeap.insert(19);
    minHeap.insert(8);
    minHeap.insert(22);
    minHeap.insert(9);

    minHeap.printHeap();
  }
}

Ausgabe:

The Min Heap is 
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7

PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90

PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8

PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15

Implementierung von Min-Heap mit PriorityQueue in Java

In diesem Programm verwenden wir PriorityQueue, die verwendet wird, um Max- und Min-Heaps zu erstellen. PriorityQueue bietet mehrere wie add(), die das Element in die Warteschlange einfügt, peek() holt den Kopf der Warteschlange und entfernt ihn, poll() ruft auch den Kopf der Warteschlange ab, ohne ihn zu entfernen. contains() prüft, ob das angegebene Element die Warteschlange ist. remove() entfernt das angegebene Element.

Wir kombinieren alle Funktionen von PriorityQueue, um Min-Heap-Operationen zu erstellen und durchzuführen. Zuerst erstellen wir ein leeres priorityQueue-Objekt vom Typ Integer mit new PriorityQueue(). Dann fügen wir unsere Elemente mit der Methode add() hinzu. Um den Kopf der Warteschlange zu drucken und zu entfernen, rufen wir priorityQueue.peek() auf, der 10 ausgibt. Dann drucken wir alle Elemente der Warteschlange mit dem erweiterten for. Jetzt rufen wir poll() auf, das 10 ausgibt und entfernt. Dann entfernen wir ein Element aus der Warteschlange. Wir verwenden contains(), das einen boolean zurückgibt, um zu prüfen, ob sich ein Element in der Warteschlange befindet. Um schließlich den verbleibenden Wert zu drucken, konvertieren wir die Warteschlange mit toArray() in ein Array.

import java.util.*;

public class JavaMinHeap {
  public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(10);
    priorityQueue.add(15);
    priorityQueue.add(25);
    priorityQueue.add(200);

    System.out.println("The head value using peek(): " + priorityQueue.peek());

    System.out.println("The queue elements: ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.poll();
    System.out.println("After removing the head element using poll(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.remove(25);
    System.out.println("After removing 25 with remove(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    boolean b = priorityQueue.contains(15);
    System.out.println("Check if priorityQueue contains 15 using contains():  " + b);

    Object[] arr = priorityQueue.toArray();
    System.out.println("Values in array: ");
    for (Object o : arr) System.out.println("Value: " + o.toString());
  }
}

Ausgabe:

The head value using peek(): 10
The queue elements: 
10
15
25
200
After removing the head element using poll(): 
15
200
25
After removing 25 with remove(): 
15
200
Check if priorityQueue contains 15 using contains():  true
Values in array: 
Value: 15
Value: 200