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.
![Min Heap in Java con esempi - 2]()
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.![Min Heap in Java con esempi - 3]()
Figura 2: heap minimo con nodi figlio sinistro > nodi figlio destro
![Min Heap in Java con esempi - 4]()
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.
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
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 ".
- 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.
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();
}
}
L'heap minimo è: [3, 13, 7, 16, 21, 12, 9] Genitore: 3 Sinistra: 13 Destra: 7 Genitore: 13 Sinistra: 16 Destra: 21 Genitore: 7 Sinistra: 12 Destra: 9 Il valore minimo is : 3 Il Min Heap è : [7, 13, 9, 16, 21, 12, 9] // dopo aver rimosso la radice Parent : 7 Left : 13 Right :9 Parent : 13 Left : 16 Right :21 Parent : 9 A sinistra: 12
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);
}
}
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