Heap: cos’è e come si gestisce in informatica

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.

Sei un webmaster? Cerchi alternative a Google Adsense per il tuo sito? Prova TheMoneytizer per il tuo sito
Usa il codice 189ed7ca010140fc2065b06e3802bcd5 per ricevere 5 € dopo l'iscrizione

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.

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

👇 Contenuti da non perdere 👇



Questo portale web esiste da 4761 giorni (13 anni), e contiene ad oggi 4108 articoli (circa 3.286.400 parole in tutto) e 24 servizi online gratuiti. – Leggi un altro articolo a caso

Numero di visualizzazioni (dal 21 agosto 2024): 11