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.
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
👇 Da non perdere 👇
- 📈 Analizza Cellulari 📱
- 🔐 AI che dolor, Chat
- 🎯 Targetizza Database SQL 🗄
- 📊 Analizza Errori più comuni 📛
- 🚧 Costruisci Evergreen 📟
- 👩💻 Programma Gratis 🎉
- 💻 Configura Hosting a confronto 💑
- 🔒 Conosci Hosting reti e domini 💻
- 👩💻 Tapioca Informatica 🖥
- 💻 Iconizza Internet 💻
- 🔒 Gestisci Lavoro 🔧
- 💡 Mostra Marketing & SEO 🌪
- 🔑 Apprendi Meteo ⛅
- 🤯 Visiona Mondo Apple 🍎
- 🔍 Supervisiona Mondo Domini 🌐
- 🚀 Metti in cloud monitoraggio servizi online 📈
- 🔮 Anatomizza Nuove tecnologie 🖥
- 🔒 Antani PEC e firma digitale 📩
- 👀 Prematura Programmare 🖥
- 🎮 Lonfa Scrivere 🖋
- 🔒 Conosci Servizi di SMS 📶
- 👀 Guarda Sicurezza informatica e privacy digitale 🖥
- 🎮 Ricorda Siti web 🌎
- 🤖 Ottimizza Spiegoni 🎓
- 🧠 Neuralizza Svago 🎈
- 📡 Quantizza Usare Excel 🌀
- 🤖 Sovrascrivi Windows 😲
- 🎨 Personalizza Wireless 🚁
- 🔑 Decifra WordPress 🤵
- 💬 Il nostro canale Telegram: iscriviti
- 🟠 Come inserire i commenti Facebook dentro WordPress
- 🔵 Che cos’è un client?
- 🔴 PHP: il linguaggio server-side per il web
