Bevor wir beginnen, wird davon ausgegangen, dass Sie sich mit einem Binärbaum auskennen (in einem Binärbaum speichert jeder Knoten einen Schlüssel, der größer als alle Schlüssel in seinem linken Teilbaum und kleiner als alle Schlüssel in seinem rechten Teilbaum ist ) . Ein binärer Heap hingegen ist ein vollständiger Binärbaum, der entweder die Ordnungseigenschaft „Min-Heap“ oder „Max-Heap“ erfüllt. Wenn Sie mit diesen Konzepten nicht vertraut sind, empfehlen wir Ihnen, diese als Voraussetzung zu verstehen. Viele unerfahrene Programmierer haben Probleme mit dem Konzept von Heaps, Min Heaps und Priority Queues. In diesem Beitrag tauchen wir ein in die Tiefe, um zu sehen, wie sich Heaps von Min-Heaps unterscheiden und wie wir Prioritätswarteschlangen verwenden können, um Min-Heaps zu implementieren.
Abbildung 1: Ein einfacher Min-Heap
Beachten Sie, dass weder im Min-Heap noch im Max-Heap eine notwendige Beziehung zwischen dem Wert eines Knotens und dem seines Geschwisterknotens besteht. Beispielsweise ist es möglich, dass die Werte für alle Knoten im linken Teilbaum der Wurzel größer sind als die Werte für jeden Knoten im rechten Teilbaum.
Abbildung 2: Min. Heap mit linken untergeordneten Knoten > rechten untergeordneten Knoten
Abbildung 3: Array-Darstellung des Heaps in Abbildung 2
Wir zeigen Ihnen, wie Sie mithilfe der folgenden Formeln einfach auf die übergeordneten, rechten oder linken untergeordneten Knoten zugreifen können.
Was ist ein Min-Heap?
Ein Min-Heap hat die Eigenschaft, dass jeder Knoten auf Ebene „n“ einen Wert speichert, der kleiner oder gleich dem seiner untergeordneten Knoten auf Ebene „n+1“ ist. Da die Wurzel einen Wert hat, der kleiner oder gleich dem Wert ihrer untergeordneten Elemente ist, die wiederum Werte haben, die kleiner oder gleich den Werten ihrer untergeordneten Elemente sind, speichert die Wurzel das Minimum aller Werte im Baum.Beispiel


Darstellung von Min Heap in Java
Die am häufigsten verwendete Datenstruktur zur Darstellung eines Min-Heaps ist ein einfaches Array. Als Anfänger müssen Sie ein „Array“ nicht mit einem „Min-Heap“ verwechseln. Man kann es sich so vorstellen, dass die Werte der Knoten/Elemente eines Min-Heaps in einem Array gespeichert werden . Genauso wie wir in Java keine Datenstruktur zum Speichern eines „ Baums “ haben und einen „Knoten“ dafür erstellen oder wie wir „Karte“ zum Speichern eines „ Diagramms “ verwenden.
- Sei minHeap[] ein ganzzahliges Array mit der Wurzel am Index „ i = 0; “.
- minHeap[(i - 1) / 2] gibt den übergeordneten Knoten zurück.
- minHeap[(i * 2) + 2] gibt den rechten untergeordneten Knoten zurück.
- minHeap[(i * 2) + 1] gibt den linken untergeordneten Knoten zurück.
Implementierung von Min Heap in Java – Verwendung von Arrays
Schauen wir uns die grundlegende Implementierung von Heaps mithilfe eines Arrays an, mit Index als aktueller Position des hinzuzufügenden Elements und Größe als Gesamtgröße des Arrays.
import java.util.Arrays;
public class MinHeap
{
private int[] Heap;
private int index;
private int size;
public MinHeap(int size) {
this.size = size;
this.index = 0;
Heap = new int[size];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return (i * 2) + 1;
}
private int rightChild(int i) {
return (i * 2) + 2;
}
private boolean isLeaf(int i) {
if (rightChild(i) >= size || leftChild(i) >= size) {
return true;
}
return false;
}
public void insert(int element) {
if (index >= size) {
return;
}
Heap[index] = element;
int current = index;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
index++;
}
// removes and returns the minimum element from the heap
public int remove() {
// since its a min heap, so root = minimum
int popped = Heap[0];
Heap[0] = Heap[--index];
minHeapify(0);
return popped;
}
// heapify the node at i
private void minHeapify(int i) {
// If the node is a non-leaf node and any of its child is smaller
if (!isLeaf(i)) {
if (Heap[i] > Heap[leftChild(i)] ||
Heap[i] > Heap[rightChild(i)]) {
if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
swap(i, leftChild(i));
minHeapify(leftChild(i));
} else {
swap(i, rightChild(i));
minHeapify(rightChild(i));
}
}
}
}
// builds the min-heap using the minHeapify
public void minHeap() {
for (int i = (index - 1 / 2); i >= 1; i--) {
minHeapify(i);
}
}
// Function to print the contents of the heap
public void printHeap() {
for (int i = 0; i < (index / 2); i++) {
System.out.print("Parent : " + Heap[i]);
if (leftChild(i) < index)
System.out.print(" Left : " + Heap[leftChild(i)]);
if (rightChild(i) < index)
System.out.print(" Right :" + Heap[rightChild(i)]);
System.out.println();
}
}
// swaps two nodes of the heap
private void swap(int x, int y) {
int tmp;
tmp = Heap[x];
Heap[x] = Heap[y];
Heap[y] = tmp;
}
public static void main(String[] arg)
{
MinHeap minHeap = new MinHeap(7);
minHeap.insert(3);
minHeap.insert(13);
minHeap.insert(7);
minHeap.insert(16);
minHeap.insert(21);
minHeap.insert(12);
minHeap.insert(9);
minHeap.minHeap();
System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
minHeap.printHeap();
System.out.println("\nThe Min Value is : " + minHeap.remove());
System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
minHeap.printHeap();
}
}
Ausgang
Der Min-Heap ist: [3, 13, 7, 16, 21, 12, 9]
Parent: 3 Left: 13 Right: 7
Parent: 13 Left: 16 Right: 21
Parent: 7 Left: 12 Right: 9
Der Min-Wert ist: 3 Der Min Heap ist: [7, 13, 9, 16, 21, 12, 9] // nach dem Entfernen der Wurzel
Parent: 7 Left: 13 Right: 9
Parent: 13 Left: 16 Right: 21
Parent: 9 Links: 12
Prioritätswarteschlangen
Eine Prioritätswarteschlange ist eine spezielle Art von Warteschlange, in der jedes Element einer Priorität zugeordnet ist und entsprechend seiner Priorität platziert wird. Für eine einfachere Implementierung von Min Heap verwenden wir die von Java bereitgestellte PriorityQueue-Klasse java.util.PriorityQueue . Wenn die angegebenen Elemente nach Priorität sortiert/platziert werden sollen, wird eine Prioritätswarteschlange verwendet. Eine Prioritätswarteschlange unterscheidet sich von einer einfachen Warteschlange, da die Standardwarteschlangen dem FIFO -Algorithmus (First-In-First-Out) folgen. Manchmal müssen die Elemente der Warteschlange jedoch entsprechend der Priorität verarbeitet werden. Aus diesem Grund wurde die Prioritätswarteschlange entwickelt. Wenn Sie Elemente zu einer Prioritätswarteschlange hinzufügen, wird standardmäßig ein minimaler Heap erstellt.Gemeinsame Operationen
Bevor wir mit der Implementierung fortfahren, finden Sie hier einige allgemeine Vorgänge in java.util.PriorityQueue , die Sie kennen müssen.- add(int element) fügt das angegebene Element in eine Prioritätswarteschlange ein.
- Remove(int Element) entfernt eine einzelne Instanz des angegebenen Elements aus dieser Warteschlange, sofern es vorhanden ist.
- peek() ruft den Kopf dieser Warteschlange ab, entfernt ihn jedoch nicht, oder gibt null zurück, wenn die Warteschlange leer ist.
- poll() ruft den Kopf dieser Warteschlange ab und entfernt ihn oder gibt null zurück, wenn diese Warteschlange leer ist.
- enthält() gibt „true“ zurück, wenn diese Warteschlange das angegebene Element enthält.
- size() gibt die Anzahl der Elemente in dieser Prioritätswarteschlange/Minheap zurück.
Implementierung von Min Heap in Java mithilfe von Priority Queues
So können Sie mithilfe der Priority Queue-Klasse von Java einen Min-Heap implementieren.
import java.util.*;
class MinHeapPriorityQueue {
static PriorityQueue minHeap = new PriorityQueue();
public static void view() {
for (Integer x : minHeap) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String args[]) {
// using "add" operation to insert elements
minHeap.add(3);
System.out.print("minHeap.add(3) = ");
view();
minHeap.add(13);
minHeap.add(7);
minHeap.add(16);
minHeap.add(21);
minHeap.add(12);
minHeap.add(9);
// printing Min-Heap
System.out.print("minHeap.view() = ");
view();
// using "peek" method to view the head
System.out.println("minHeap.peek() = " + minHeap.peek());
// using "poll" method to remove and retrieve the head
minHeap.poll();
System.out.print("minHeap.poll() = ");
view();
// using "remove" method to remove specified element
minHeap.remove(7);
System.out.print("minHeap.remove(7) = ");
view();
// Check if an element is present using contains()
boolean elementFound = minHeap.contains(11);
System.out.println("minHeap.contains(11) = " + elementFound);
elementFound = minHeap.contains(16);
System.out.println("minHeap.contains(16) = " + elementFound);
}
}
Ausgang
minHeap.add(3) = 3
minHeap.view() = 3 13 7 16 21 12 9
minHeap.peek() = 3
minHeap.poll() = 7 13 9 16 21 12
minHeap.remove(7) = 9 13 12 16 21
minHeap.contains(11) = false
minHeap.contains(16) = true
GO TO FULL VERSION