Heap binario: differenze tra le versioni

Versione delle 15:54, 4 giu 2021

Versione delle 02:14, 15 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' semplici, se il nodo A e' genitore del nodo B, allora il nodo A ha maggior priorita' di A. Uno heap binario puo' essere definito in modo che le chiavi piu' prioritarie siano quelle piu' piccole (si parla di Heap a minimo) oppure in modo che le chiavi piu' priotarie siano le piu' grandi (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.