Min Heap in Java con esempi

Prima di iniziare, si presume che tu conosca un albero binario (in un albero binario, ogni nodo memorizza una chiave maggiore di tutte le chiavi nel suo sottoalbero sinistro e minore di tutte le chiavi nel suo sottoalbero destro ) . Considerando che un Heap binario è un albero binario completo che soddisfa la proprietà di ordinamento min-heap o max-heap. Se non hai familiarità con questi concetti, ti consigliamo di capirli come prerequisito. Molti programmatori alle prime armi possono avere problemi con il concetto di heap, min heap e code prioritarie. In questo post faremo un'analisi approfondita per vedere in che modo gli heap sono diversi dai Min-Heap e come possiamo utilizzare le code prioritarie per implementare i Min Heap.

Che cos'è un mucchio minimo?

Un min-heap ha la proprietà che ogni nodo al livello 'n' memorizza un valore che è minore o uguale a quello dei suoi figli al livello 'n+1'. Poiché la radice ha un valore minore o uguale ai suoi figli, che a loro volta hanno valori minori o uguali ai loro figli, la radice memorizza il minimo di tutti i valori nell'albero.

Esempio

Figura 1: un semplice heap minimo Si noti che non esiste una relazione necessaria tra il valore di un nodo e quello del suo fratello nel min-heap o nel max-heap. Ad esempio, è possibile che i valori per tutti i nodi nel sottoalbero sinistro della radice siano maggiori dei valori per ogni nodo del sottoalbero destro. Figura 2: heap minimo con nodi figlio sinistro > nodi figlio destro

Rappresentazione di Min Heap in Java

La struttura dati più comunemente usata per rappresentare un Min Heap è un semplice Array. Come principiante non è necessario confondere un "array" con un "min-heap". Puoi vederlo come, i valori dei nodi/elementi di un min-heap sono memorizzati in un array . Proprio come non abbiamo alcuna struttura dati per memorizzare un " albero " in Java e costruiamo un "nodo" per esso, o il modo in cui usiamo "map" per memorizzare un " grafo ". Figura 3: rappresentazione in matrice dell'heap nella figura 2 Dimostreremo come è possibile accedere semplicemente ai nodi figlio padre, destro o sinistro utilizzando le seguenti formule.

• Lascia che minHeap[] sia un array intero con root all'indice “ i = 0; ”.
• minHeap[(i - 1) / 2] restituisce il nodo padre.
• minHeap[(i * 2) + 2] restituisce il nodo figlio destro.
• minHeap[(i * 2) + 1] restituisce il nodo figlio sinistro.

Considerando la figura n. 2 sopra riportata, il valore di root (genitore) = 3, il nodo figlio sinistro è 13 e il nodo figlio destro = 7.

Implementazione di Min Heap in Java - Utilizzo di array

Diamo un'occhiata all'implementazione di base di Heaps utilizzando l'array, con index come posizione corrente dell'elemento da aggiungere e size come dimensione totale dell'array.

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

Produzione

Code prioritarie

Una coda prioritaria è un tipo speciale di coda in cui ogni elemento è associato a una priorità e viene posizionato in base alla sua priorità. Per un'implementazione più semplice di min heap, utilizziamo la classe PriorityQueue java.util.PriorityQueue fornita da Java. Se gli elementi dati devono essere ordinati/posizionati in una priorità, viene utilizzata una coda prioritaria. Una coda prioritaria è diversa da una coda semplice perché le code standard seguono l'algoritmo FIFO (First-In-First-Out ), ma a volte gli elementi della coda devono essere elaborati in base alla priorità, ecco perché è stata progettata la coda prioritaria. Quando aggiungi elementi a una coda di priorità, per impostazione predefinita viene creato un heap minimo.

Operazioni comuni

Prima di passare all'implementazione, ecco alcune operazioni comuni in java.util.PriorityQueue che è necessario conoscere.

• add(int element) inserisce l'elemento specificato in una coda di priorità.
• remove(int element) rimuove una singola istanza dell'elemento specificato da questa coda, se presente.
• peek() recupera, ma non rimuove, l'intestazione di questa coda o restituisce null se la coda è vuota.
• poll() recupera e rimuove l'intestazione di questa coda o restituisce null se questa coda è vuota.
• contains() restituisce "true" se questa coda contiene l'elemento specificato.
• size() restituisce il numero di elementi in questa coda di priorità/minheap.

Implementazione di Min Heap in Java utilizzando le code prioritarie

Ecco come implementare un heap minimo utilizzando la classe della coda di priorità di 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);
	}
}

Produzione

Conclusione

Gli heap min sono ampiamente utilizzati per recuperare l'elemento più piccolo in un pool di elementi in tempo costante. Esistono molte altre applicazioni di questa struttura dati, tuttavia puoi scegliere qualsiasi metodo per implementarlo. Inutile dire che devi esercitarti con pazienza per diventare bravo. Quindi mettiamo in moto i nostri muscoli e mettiamoci al lavoro!