Un heap è una struttura di dati. È una specie di albero con l'interessante proprietà che ogni nodo ha un valore più basso di qualsiasi suo figlio.
Questo gli dà solo un ordine parziale, quindi se vuoi trovare un valore specifico nell'heap, non è facile. Questo è un grande svantaggio rispetto ad un albero binario, che permette di fare ricerche efficienti.
Ma il vantaggio di allentare questo vincolo è la velocità. Può fare inserimenti e rimozioni in tempo log n, e si può visualizzare il valore minimo in tempo costante.
Un suo utilizzo è un heap sort. Funziona così
- mettere tutti i vostri valori in un heap
- Rimuoverli da un heap
E' un efficiente in place nlgn sort. Mettere i valori in un heap dà loro un ordine sciolto, ma il valore più basso è sempre alla radice, così quando li rimuovi restituisce i valori in ordine.
È anche una buona scelta per implementare una coda di priorità. Si aggiungono valori in base alla loro priorità, e li si ottiene indietro in ordine di priorità. Questo è molto più efficiente che cercare di mantenere una lista ordinata ad ogni passo.