Heap: cos’è e come si gestisce in informatica

Aggiornato il: 11-01-2023 11:30
In informatica l’heap è una delle più note e studiate strutture dati, di cui sono disponibili numerose varianti a seconda delle necessità. Assieme allo stack è una delle strutture dati più funzionali, note ed importanti ad una incredibile molteplicità di applicazioni diverse tra loo. Letteralmente la parola heap significa “mucchio”, e la sua caratteristica è che può essere rappresentato mediante una struttura nota come albero binario: ogni nodo dell’albero è, nello specifico, in relazione predefinita genitore-figlio, per cui se colleghiamo direttamente, come avviene di seguito, il nodo 100 con il nodo 19, significa che tra 100 e 19 esiste una relazione di un certo tipo.





L’utilità dell’heap emerge soprattutto negli algoritmi di ordinamento più efficenti (es. heap sort), cosa di cui ci possiamo accorgere facilmente se andiamo a vedere la versione linearizzata dell’albero che sarà, nello specifico, una lista ordinata.

Max Heap new.svg
By Kelott – Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=99968794

Dettagli tecnici sul funzionamento dell’heap

La struttura dei dati dell’heap, in particolare l’heap binario, è stata introdotta da J. W. J. Williams nel 1964, come struttura dei dati per l’algoritmo di ordinamento heapsort.

A livello più approfondito un heap è una struttura dati basata su albero binario (binary tree), che è essenzialmente un albero quasi-completo che soddisfa la proprietà per cui:

  • in un max-heap, per un qualsiasi nodo F, se P è il nodo padre di F allora la chiave o il valore di P è maggiore o uguale alla chiave (o al valore) di F.
  • In un min-heap, al contrario, la chiave di P è minore o uguale alla chiave di F.

Negli alberi heap il nodo nella parte superiore dell’heap, l’unico privo di nodo-genitore, è chiamato nodo radice (root).

L’heap è un’implementazione estremamente efficiente di una coda di priorità e, in effetti, le code di priorità sono spesso chiamate “heap”, indipendentemente dal fatto che facciano uso di un heap. In un heap, l’elemento con priorità più alta (o più bassa) viene sempre messo nella root. Un heap è una struttura di dati utile nel caso in cui sia necessario rimuovere più volte l’oggetto con la priorità più alta (o più bassa), o qualora gli inserimenti devono essere intervallati da rimozioni del nodo radice.

Un’implementazione comune di un heap è l’heap binario, in cui l’albero è un albero binario.

Gli heap sono anche cruciali in diversi algoritmi grafici efficienti come l’algoritmo di Dijkstra.

Operazioni ammissibili su un heap

Sugli heap sono disponibili ed implementabili vari tipi di funzioni base, tra cui ad esempio:

  • ricerca del massimo valore o chiave;
  • ricerca del minimo valore o chiave;
  • inserimento di un nodo;
  • estrazione e/o rimozione di un nodo;
  • sostituzione di un nodo;
  • creazione di un albero vuoto;
  • merge tra due alberi binari;
  • creazione di un albero heap a partire da una lista;
  • dimensione dell’heap (restituisce la dimensione, ovvero il numero di nodi, come intero positivo).

Come si usa l’heap nella pratica

La struttura dei dati dell’heap presenta molteplici applicazioni pratiche:

  • Heapsort: algoritmo di ordinamento efficente
  • selezione in tempo sublineare di minimo e massimo nodo
  • copertura minima di Prim
  • cammini minimi di Dijkstra
  • gestione di code prioritarie
  • algoritmi in uso nelle statistiche

Photo by Rick Mason on Unsplash



Questo blog pubblica contenuti ed offre servizi free da 11 anni. – Leggi un altro articolo a caso – Per informazioni contattaci
Non ha ancora votato nessuno.

Ti sembra utile o interessante? Vota e fammelo sapere.

Heap: cos’è e come si gestisce in informatica
rick mason 2FaCKyEEtis unsplash scaled
Torna su