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.
Usa il codice
189ed7ca010140fc2065b06e3802bcd5
per ricevere 5 € dopo l'iscrizioneL’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.

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:
Scopri i servizi del sito 👇
- 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 👇
- Lavoro 🔧
- Marketing & SEO 🌪
- Mondo Apple 🍎
- Reti 💻
- Scrivere 🖋
- Sicurezza & Privacy 👁
- Spiegoni artificiali 🎓
- Svago 🎈
- 💬 Il nostro canale Telegram: iscriviti
- 🔴 Che significa deepfake?
- 🟢 Cosa sono le pagine ASP (Active Server Pages)?
- 🟠 Temu: cos’è e come funziona