Sommario:
Definizione - Cosa significa Heap?
Un heap, nel contesto della struttura dei dati, è una struttura di dati basata su albero che soddisfa la proprietà heap, in cui a ciascun elemento viene assegnato un valore chiave o ponderazione. La chiave di valore inferiore ha sempre un nodo padre con una chiave di valore superiore. Questa è chiamata struttura heap max e, tra tutti i nodi, il nodo radice ha la chiave più alta.
A volte, una struttura basata su albero ha una regola di struttura invertita, in cui un elemento con una chiave di valore superiore ha sempre una chiave di valore inferiore come nodo padre. Questa è chiamata struttura heap min e, tra tutti i nodi, il nodo radice ha la chiave più bassa.
Techopedia spiega Heap
Non ci sono restrizioni pratiche sul numero di figli che ogni nodo può avere in un heap, anche se di solito ogni nodo ne ha due al massimo. L'heap è considerata l'implementazione più efficiente di un tipo di dati astratto, noto come coda di priorità. L'implementazione dell'heap è essenziale in vari algoritmi grafici (incluso l'algoritmo di Dijkstra) e nell'algoritmo di ordinamento heapsort.
Gli heap presentano diverse varianze che agiscono come implementazioni di code di priorità dei tipi di dati astratte con elevata efficienza. Molte applicazioni, come gli algoritmi grafici, richiedono l'implementazione di code prioritarie.
Un array è la forma di implementazione dell'heap più comune, in cui non sono necessari puntatori per collegarsi tra i suoi elementi.
Gli heap eseguono più operazioni, tra cui:
- Find-max: cerca il nodo chiave più alto tra un gruppo di nodi
- Find-min: cerca il nodo chiave più basso tra un gruppo di nodi
- Delete-max: elimina il nodo chiave più alto tra un gruppo di nodi
- Delete-min: elimina il nodo chiave più basso tra un gruppo di nodi
Gli heap includono anche funzioni che eseguono l'unione, l'inserimento e le modifiche chiave.
Questa definizione è stata scritta nel contesto della struttura dei dati
