Heap binario: differenze tra le versioni

Versione delle 21:16, 3 apr 2006

Versione delle 21:18, 3 apr 2006

Riga 1:

Un '''heap''' è una [[struttura dati]] utilizzata in informatica, più precisamente un [[albero binario]] completo usato principalmente per la memorizzazione di collezioni di dati, dette [[Dizionario|dizionari]].

In ogni nodo è presente una coppia ''(k,x)'' in cui ''k'' è il valore della chiave associata alla entry ''x''. Nei dizionari, a differenza delle [[Hash|mappe]], ogni chiave può essere associata a più entry (come in un "reale" dizionario ogni parola ha più significati).</br>

Questi tipi di albero hanno la caratteristica secondo la quale qualsiasi nodo padre ha chiave minore di entrambi (se esistono) i suoi figli.</br>

In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo ''v'' dell'albero e scendendo nella struttura verso le foglie, si attraaversano nodi con chiave sempre crescente (in senso lato).