Heap binario: differenze tra le versioni

Versione delle 08:30, 19 mag 2015

Versione delle 21:23, 24 mag 2015

Riga 3:

{{Avvisounicode}}

{{Strutture dati lineari}}

[[File:HeapVector.PNG|thumb|right|Implementazione di un heap (min-heap) mediante Vettore]]

Un '''heap binario''', è una [[struttura dati]] utilizzata in [[informatica]], più precisamente un vettore o una lista che soddisfi la proprietà heap. Un heap binario può essere visto, per comodità di rappresentazione, come un [[albero binario]] quasi completo. È usato principalmente per la raccolta di collezioni di dati, dette dizionari, e per la rappresentazione di [[code di priorità]].

Dato j, indice ad un nodo della heap, si definiscono '''Padre di j''' il nodo in posizione j/2, '''Figlio sinistro di j''' il nodo in posizione j*2 e '''Figlio destro di j''' il nodo in posizione j*2+1. Si possono quindi definire le funzioni Padre(j), FiglioSX(j), FiglioDX(j) che rispettivamente restituiscono l'indice del padre, del figlio sinistro e del figlio destro di j. Spesso sono implementate come macro o funzioni in linea.

Esistono due tipi di heap: '''min-heap''' e '''max-heap'''. La scelta di utilizzare un tipo di heap anziché l'altro è data dal tipo di impiego che se ne vuole fare.<br />

Condizioni '''Heap''': dato j indice di posizione della struttura e v lo heap preso in considerazione