Heap binario: differenze tra le versioni

Versione delle 23:27, 5 feb 2024

Versione delle 11:39, 23 gen 2025

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à]]. 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.

Riga 65:

== Inserimento di un valore ==

Vediamo ora una rassegna dei principali metodi che sono associati ad una [[coda di priorità]], ovvero una [[struttura dati]] in cui in ogni momento è possibile associare una priorità alle entry che ne fanno parte.

In primo luogo analizziamo il metodo ''insert'', attraverso il quale, come dice il nome stesso, si inserisce un nuovo nodo all'interno dell'albero:

<pre>