heap binario

Uno heap binario, è uno 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à. Lo 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 più semplici, se il nodo A è genitore del nodo B, allora il nodo A ha maggior priorità di B. Uno heap binario può essere definito in modo che le chiavi più prioritarie siano quelle più piccole (si parla di heap a minimo) oppure in modo che le chiavi più prioritarie siano le più 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.