Implementazione della struttura dati Max Heap in Java

Implementazione della Struttura Dati Max Heap in Java

Introduzione

Un Max Heap è una struttura dati ad albero binario completo che soddisfa la proprietà di Heap, ovvero ogni nodo è maggiore o uguale ai suoi figli. Trova applicazione in vari algoritmi come l’ordinamento, la ricerca e la selezione.

Questa guida fornisce una dettagliata implementazione della struttura dati Max Heap in Java, esplorandone i metodi chiave, le operazioni e le considerazioni sulle prestazioni.

Implementazione

Classe MaxHeap

java
public class MaxHeap {
private int[] heap;
private int size;

// Costruisce un Heap vuoto
public MaxHeap() {
this.heap = new int[10];
this.size = 0;
}

// Costruisce un Heap da un array
public MaxHeap(int[] arr) {
this.heap = arr;
this.size = arr.length;
buildHeap();
}

// Ripristina la proprietà di Heap
private void buildHeap() {
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(i);
}
}

// Ripristina la proprietà di Heap in un subalbero radicato in un indice specificato
private void heapify(int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < size && heap[left] > heap[largest]) {
largest = left;
}

if (right < size && heap[right] > heap[largest]) {
largest = right;
}

if (largest != i) {
swap(i, largest);
heapify(largest);
}
}

// Scambia due elementi nell'heap
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}

// Inserisce un elemento nell'heap
public void insert(int element) {
if (size == heap.length) {
resize(2 * size);
}

heap[size++] = element;
int i = size - 1;

while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}

// Rimuove il nodo radice dall'heap
public int extractMax() {
if (size == 0) {
throw new RuntimeException("Heap vuoto");
}

int max = heap[0];
heap[0] = heap[size - 1];
size--;

heapify(0);

return max;
}

// Ridimensiona l'heap
private void resize(int newSize) {
int[] newHeap = new int[newSize];
System.arraycopy(heap, 0, newHeap, 0, size);
heap = newHeap;
}

// Ottiene il nodo radice
public int getMax() {
if (size == 0) {
throw new RuntimeException("Heap vuoto");
}

return heap[0];
}

// Ottiene la dimensione dell'heap
public int getSize() {
return size;
}

// Controlla se l'heap è vuoto
public boolean isEmpty() {
return size == 0;
}
}


Operazioni

Inserimento

Per inserire un elemento in un Max Heap, utilizza il metodo insert:

java
heap.insert(element);


Rimozione

Per rimuovere l’elemento radice (massimo) dall’heap, utilizza il metodo extractMax:

java
int max = heap.extractMax();


Recupero del Nodo Radice

Per recuperare l’elemento radice (massimo) senza rimuoverlo, utilizza il metodo getMax:

java
int max = heap.getMax();


Ottenimento della Dimensione

Per ottenere il numero di elementi nell’heap, utilizza il metodo getSize:

java
int size = heap.getSize();


Controllo della Vuotezza

Per controllare se l’heap è vuoto, utilizza il metodo isEmpty:

java
boolean isEmpty = heap.isEmpty();


Considerazioni sulle Prestazioni

* Inserimento: O(log(n)), dove n è il numero di elementi nell’heap.
* Rimozione: O(log(n)).
* Recupero del Nodo Radice: O(1).
* Ottenimento della Dimensione: O(1).
* Controllo della Vuotezza: O(1).

Conclusione

L’implementazione di Max Heap in Java presentata in questa guida fornisce una solida struttura dati per gestire insiemi di dati di grandi dimensioni. L’attenzione alla proprietà di Heap garantisce tempi di accesso rapidi per le operazioni di inserimento, rimozione e recupero del nodo radice. Il ridimensionamento automatico garantisce inoltre l’efficienza anche con insiemi di dati in crescita. Comprendendo e utilizzando correttamente Max Heap, gli sviluppatori possono migliorare le prestazioni delle loro applicazioni.

FAQ

1. Cos’è un Max Heap?
– Un Max Heap è un albero binario completo in cui ciascun nodo è maggiore o uguale ai suoi figli.

2. A cosa serve un Max Heap?
– I Max Heap trovano applicazione in algoritmi di ordinamento (Heap Sort), ricerca e selezione del massimo.

3. Come si inserisce un elemento in un Max Heap?
– Si chiama il metodo insert per inserire un elemento, che lo posiziona correttamente mantenendo la proprietà di Heap.

4. Come si rimuove il nodo radice da un Max Heap?
– Si chiama il metodo extractMax per rimuovere e restituire l’elemento radice (massimo), mantenendo la proprietà di Heap.

5. Come si ottiene il nodo radice senza rimuoverlo?
– Si chiama il metodo getMax per restituire il nodo radice mantenendolo nell’heap.

6. Come si ottiene la dimensione di un Max Heap?
– Si chiama il metodo getSize per ottenere il numero di elementi nell’heap.

7. Come si controlla se un Max Heap è vuoto?
– Si chiama il metodo isEmpty per verificare se l’heap contiene elementi.

8. Quali sono le considerazioni sulle prestazioni di un Max Heap?
– Le operazioni di inserimento e rimozione hanno una complessità temporale di O(log(n)), mentre il recupero del nodo radice, l’ottenimento della dimensione e il controllo della vuotezza hanno una complessità costante O(1).