Min. Heap in Java mit Beispielen

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.

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

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

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. 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.

• 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.

In Anbetracht der oben angegebenen Abbildung Nr. 2 ist der Wert der Wurzel (übergeordneter Knoten) = 3, der linke untergeordnete Knoten ist 13 und der rechte untergeordnete Knoten ist = 7.

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

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

Abschluss

Min-Heaps werden häufig verwendet, um das kleinste Element in einem Elementpool in konstanter Zeit abzurufen. Es gibt viele andere Anwendungen dieser Datenstruktur, Sie können jedoch eine beliebige Methode zur Implementierung wählen. Es versteht sich von selbst, dass man mit Geduld üben muss, um gut darin zu werden. Also lasst uns unsere Muskeln in Schwung bringen und uns an die Arbeit machen!