Heap binario: differenze tra le versioni

Versione delle 02:14, 15 giu 2021

Versione delle 11:16, 29 giu 2021

Riga 2:

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

Uno '''heap binario''', è uno [[Heap (struttura dati)|heap]] sviluppato su un [[albero binario]]. È usato principalmente per la raccolta di collezioni di dati, dette dizionari, e per la rappresentazione di [[code di priorità]]. L'heap binario deve sottostare alle seguenti condizioni:

*Condizione di heap: se A è un genitore di B, allora la chiave di A è ordinata rispetto alla chiave di B conformemente alla relazione d'ordine applicata all'intero heap. In parole piu'più semplici, se il nodo A e'è genitore del nodo B, allora il nodo A ha maggior priorita'priorità di A. Uno heap binario puo'può essere definito in modo che le chiavi piu'più prioritarie siano quelle piu'più piccole (si parla di Heap''heap a minimo'') oppure in modo che le chiavi piu'più priotarie siano le piu'più grandi (Heap''heap a massimo'').

*Condizione di forma: tutti i livelli dello heap, tranne eventualmente l'ultimo, devono essere completi; se l'ultimo livello non è completo, i nodi devono essere disposti —per convenzione— a partire dall'estrema sinistra.