Heap binario: differenze tra le versioni

Versione delle 11:39, 23 gen 2025

Versione attuale delle 19:53, 2 feb 2025

Riga 3:

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à]]. 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. Questo significa che, nell'ultimo livello, i nodi vengono aggiunti nel primo spazio vuoto a partire dalla sinistra.

== Implementazione con array ==