Un heap binario è un albero binario in cui ogni nodo ha chiave maggiore(minore) di quelle dei suoi figli.
La struttura dell'heap è gerarchica, essendo esso un albero binario. Ciò che può essere fuorviante è che tale struttura ad albero binario può essere memorizzata in un array A, in cui A[0] rappresenta la radice, e i generici figli del nodo in posizione i si trovano alle posizioni 2i+1 (figlio sinistro) e 2i+2 (figlio destro). Ciò è vero nel caso che il linguaggio che utilizzi faccia iniziare gli array dalla posizione 0 come il C o il Java.
Nel caso gli array partano da 1, come in Pascal, le posizioni saranno 2i e 2i+1.
Una coda a priorità indica invece un ordinamento tra un insieme di elementi, secondo la priorità di tali elementi.
Va di suo che un heap è particolarmente efficace per realizzare una coda a priorità in quanto l'estrazione dall'insieme dell'elemento con priorità massima può essere fatto in tempo costante, in quanto nella radice dell'heap ci sarà sempre l'elemento con priorità massima.
Mentre il ripristino della proprietà heap può essere fatta in tempo logaritmico.
ciao ciao
