Cos'è heap?

Heap (Struttura Dati)

Un heap (o monte binario) è una struttura dati ad albero specializzata che soddisfa la proprietà dell'heap: se A è un nodo genitore di B, allora la chiave (il valore) del nodo A è ordinata in relazione alla chiave del nodo B con lo stesso ordine applicato a tutti i nodi nell'heap. Questo implica che il nodo con la chiave "migliore" è sempre il nodo radice.

Gli heap sono in genere implementati come alberi binari, anche se in alcuni casi possono essere implementati con alberi n-ari. Esistono due tipi principali di heap binari:

• Min Heap: In un min heap, il valore della chiave di ogni nodo è minore o uguale al valore della chiave dei suoi figli. Il nodo radice contiene quindi l'elemento con la chiave minima. Puoi trovare maggiori informazioni sul concetto di Min%20Heap.

• Max Heap: In un max heap, il valore della chiave di ogni nodo è maggiore o uguale al valore della chiave dei suoi figli. Il nodo radice contiene quindi l'elemento con la chiave massima. Puoi trovare maggiori informazioni sul concetto di Max%20Heap.

Proprietà Importanti:

• Forma: Un heap binario è un albero binario completo. Ciò significa che tutti i livelli sono completamente riempiti, ad eccezione eventualmente dell'ultimo livello, che viene riempito da sinistra a destra. Questa proprietà permette di rappresentare un heap in modo efficiente usando un array. Puoi saperne di più sulla Rappresentazione%20ad%20Array%20di%20un%20Heap.

• Complessità Temporale: Le operazioni comuni su un heap (inserimento, eliminazione del massimo/minimo, modifica della chiave) hanno una complessità temporale di O(log n), dove n è il numero di elementi nell'heap. Per approfondire puoi consultare Complessità%20Temporale%20Heap.

Utilizzi Comuni:

• Heap Sort: Un algoritmo di ordinamento efficiente basato sulla struttura dati heap. Informazioni aggiuntive su Heap%20Sort.
• Coda di Priorità: Gli heap sono spesso utilizzati per implementare le code di priorità, dove gli elementi vengono serviti in base alla loro priorità. Puoi leggere di più su Code%20di%20Priorità.
• Algoritmo di Dijkstra: L'algoritmo di Dijkstra per trovare il cammino più breve in un grafo può essere implementato in modo efficiente utilizzando un min heap. Approfondisci su Algoritmo%20di%20Dijkstra.

Operazioni di Base:

• Inserimento (Insert): Aggiunge un nuovo elemento all'heap.
• Estrazione del massimo/minimo (Extract Max/Min): Rimuove e restituisce l'elemento con la chiave più grande (in un max heap) o la chiave più piccola (in un min heap).
• Heapify: Trasforma un albero binario in un heap. Per capire meglio vedi Heapify.
• Aumento/Diminuzione della chiave (Increase/Decrease Key): Modifica il valore della chiave di un elemento e ripristina la proprietà dell'heap.