Cos'è una pila (nel contesto delle strutture dati)?

Un heap è un albero specializzato usato come struttura dati. La proprietà principale dell'heap è l'ordinamento parziale: per ogni vertice, la condizione è che il valore del vertice genitore sia maggiore o uguale a quello di uno qualsiasi dei suoi figli (max-heap) o minore o uguale (min-heap).

Caratteristiche principali:

• Albero binario: Viene generalmente implementato come un albero binario, dove ogni nodo ha al massimo due figli.
• Albero binario completo: Su tutti i livelli, tranne forse l'ultimo, l'albero è completamente riempito. I nodi dell'ultimo livello vengono riempiti da sinistra a destra. Questo permette di memorizzare efficacemente l'heap come un array.
• Proprietà dell'heap:
  • Max-heap: Il valore di ogni nodo è maggiore o uguale a quello dei suoi figli. L'elemento massimo si trova sempre alla radice.
  • Min-heap: Il valore di ogni nodo è minore o uguale a quello dei suoi figli. L'elemento minimo si trova sempre alla radice.

Operazioni principali con l'heap:

• Inserimento di un elemento: Aggiunta di un nuovo elemento e mantenimento della proprietà dell'heap.
• Eliminazione di un elemento: Rimozione dell'elemento radice (massimo o minimo, a seconda del tipo di heap) e mantenimento della proprietà dell'heap.
• Costruzione dell'heap: Costruzione di un heap da un array di elementi.

Applicazioni dell'heap:

• Ordinamento: Algoritmo di ordinamento con heap (Heapsort).
• Code di priorità: Implementazione efficiente di code in cui gli elementi vengono elaborati in ordine di priorità.
• Algoritmi di ricerca: Per esempio, ricerca del k-esimo elemento per valore.
• Algoritmi sui grafi: Per esempio, l'algoritmo di Dijkstra.

Rappresentazione dell'heap in array:

Poiché l'heap è un albero binario completo, può essere memorizzato efficacemente in un array senza usare puntatori.

• Se un nodo si trova all'indice i, il suo figlio sinistro si trova all'indice 2*i + 1.
• Il suo figlio destro si trova all'indice 2*i + 2.
• Il suo genitore si trova all'indice (i - 1) / 2.

# Esempio di rappresentazione di un min-heap come array
heap_array = [10, 15, 20, 17, 25, 30]

# Radice: heap_array[0] = 10
# Figlio sinistro della radice: heap_array[2*0 + 1] = heap_array[1] = 15
# Figlio destro della radice: heap_array[2*0 + 2] = heap_array[2] = 20
# Genitore dell'elemento all'indice 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15