Cos'è una pila?

Un heap è una struttura dati ad albero speciale che soddisfa la proprietà del heap. Questa proprietà afferma che per ogni vertice, tranne la radice, il valore della chiave di quel vertice deve essere in una certa relazione con il valore della chiave del suo genitore. Esistono due principali tipi di heap:

• Max-heap: Il valore della chiave di ogni vertice non è inferiore a quello dei suoi figli. L'elemento massimo si trova alla radice.
• Min-heap: Il valore della chiave di ogni vertice non è superiore a quello dei suoi figli. L'elemento minimo si trova alla radice.

Il heap viene generalmente implementato come un array, il che permette un accesso efficiente agli elementi e l'esecuzione di operazioni. La relazione tra genitori e figli nell'array è la seguente:

• Per un elemento con indice i (a partire da 0), il suo figlio sinistro si trova all'indice 2i + 1.
• Il suo figlio destro si trova all'indice 2i + 2.
• Il suo genitore si trova all'indice floor((i - 1) / 2).

Operazioni principali sul heap:

• Inserimento: Aggiunta di un nuovo elemento. Tempo di esecuzione O(log n), dove n è il numero di elementi.
• Estrazione-Max / Estrazione-Min: Rimozione e restituzione dell'elemento massimo (in un max-heap) o minimo (in un min-heap). Tempo di esecuzione O(log n).
• Heapify (Costruzione dell'heap): Trasformazione di un array arbitrario in un heap. Tempo di esecuzione O(n).

Gli heap sono utilizzati negli algoritmi di ordinamento (ad esempio, ordinamento con heap), nelle code di priorità e negli algoritmi di ricerca dei percorsi più brevi (ad esempio, l'algoritmo di Dijkstra).