Min Heap en Java avec des exemples

Avant de commencer, on suppose que vous connaissez un arbre binaire (dans un arbre binaire, chaque nœud stocke une clé supérieure à toutes les clés de son sous-arbre gauche et inférieure à toutes les clés de son sous-arbre droit ) . Considérant qu'un tas binaire est un arbre binaire complet qui satisfait la propriété d'ordre min-heap ou max-heap. Si vous n'êtes pas familier avec ces concepts, nous vous recommandons de les comprendre comme condition préalable. De nombreux programmeurs novices peuvent avoir du mal avec le concept de Heaps, Min Heaps et Priority Queues. Dans cet article, nous allons plonger en profondeur pour voir en quoi les tas sont différents des Min-Heaps et comment nous pouvons utiliser les files d'attente prioritaires pour implémenter Min Heaps.

Qu'est-ce qu'un tas minimal ?

Un min-heap a la propriété que chaque nœud au niveau 'n' stocke une valeur inférieure ou égale à celle de ses enfants au niveau 'n+1'. Étant donné que la racine a une valeur inférieure ou égale à ses enfants, qui à leur tour ont des valeurs inférieures ou égales à leurs enfants, la racine stocke le minimum de toutes les valeurs dans l'arborescence.

Exemple

Figure 1 : Un simple tas min Notez qu'il n'y a pas de relation nécessaire entre la valeur d'un nœud et celle de son frère dans le tas min ou le tas max. Par exemple, il est possible que les valeurs de tous les nœuds du sous-arbre gauche de la racine soient supérieures aux valeurs de chaque nœud du sous-arbre droit. Figure 2 : Tas minimal avec nœuds enfants gauches > nœuds enfants droits

Représentation de Min Heap en Java

La structure de données la plus couramment utilisée pour représenter un Min Heap est un simple Array. En tant que débutant, vous n'avez pas besoin de confondre un "tableau" avec un "min-tas". Vous pouvez le voir comme, les valeurs des nœuds/éléments d'un min-heap sont stockées dans un tableau . Tout comme nous n'avons pas de structure de données pour stocker un " arbre " en Java et nous construisons un "nœud" pour cela, ou la façon dont nous utilisons "map" pour stocker un " graphe ". Figure 3 : représentation matricielle du tas dans la figure 2 Nous allons montrer comment vous pouvez accéder simplement aux nœuds parent, enfant droit ou gauche à l'aide des formules suivantes.

• Soit minHeap[] est un tableau d'entiers avec racine à l'index " i = 0 ; ”.
• minHeap[(i - 1) / 2] renvoie le nœud parent.
• minHeap[(i * 2) + 2] renvoie le nœud enfant droit.
• minHeap[(i * 2) + 1] renvoie le nœud enfant gauche.

Considérant la figure # 2 donnée ci-dessus, la valeur de la racine (parent) = 3, le nœud enfant gauche est 13 et le nœud enfant droit = ​​7.

Implémentation de Min Heap en Java - Utilisation de tableaux

Examinons l'implémentation de base de Heaps en utilisant array, avec index comme position actuelle de l'élément à ajouter et size comme taille totale du tableau.

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();
	}
}

Sortir

Files d'attente prioritaires

Une file d'attente prioritaire est un type spécial de file d'attente dans laquelle chaque élément est associé à une priorité et est placé en fonction de sa priorité. Pour une implémentation plus facile du tas min, nous utilisons la classe PriorityQueue java.util.PriorityQueue fournie par Java. Si les éléments donnés sont censés être triés/placés dans une priorité, une file d'attente prioritaire est utilisée. Une file d'attente prioritaire est différente d'une simple file d'attente car les files d'attente standard suivent l'algorithme First-In-First-Out ( FIFO ), mais parfois les éléments de la file d'attente doivent être traités en fonction de la priorité, c'est pourquoi la file d'attente prioritaire est conçue. Lorsque vous ajoutez des éléments à une file d'attente prioritaire, un tas min est créé par défaut.

Opérations courantes

Avant de passer à l'implémentation, voici quelques opérations courantes dans java.util.PriorityQueue que vous devez connaître.

• add(int element) insère l'élément spécifié dans une file d'attente prioritaire.
• remove(int element) supprime une seule instance de l'élément spécifié de cette file d'attente, si elle est présente.
• peek() récupère, mais ne supprime pas, la tête de cette file d'attente, ou renvoie null si la file d'attente est vide.
• poll() récupère et supprime la tête de cette file d'attente, ou renvoie null si cette file d'attente est vide.
• contains() renvoie "true" si cette file d'attente contient l'élément spécifié.
• size() renvoie le nombre d'éléments dans cette file d'attente prioritaire/minheap.

Implémentation de Min Heap en Java à l'aide de files d'attente prioritaires

Voici comment vous pouvez implémenter un tas min en utilisant la classe de file d'attente prioritaire par java.

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);
	}
}

Sortir

Conclusion

Les tas min sont largement utilisés pour récupérer le plus petit élément d'un pool d'éléments en temps constant. Il existe de nombreuses autres applications de cette structure de données, mais vous pouvez choisir n'importe quelle méthode pour l'implémenter. Inutile de dire qu'il faut s'entraîner avec patience pour devenir bon. Alors bougeons nos muscles et mettons-nous au travail !