Heap binario: differenze tra le versioni

Versione delle 12:36, 18 apr 2023

Versione attuale delle 19:53, 2 feb 2025

(3 versioni intermedie di 2 utenti non mostrate)

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

== Implementazione con array ==

Riga 21:

== Code di priorità ==

{{Vedi anche|Coda di priorità}}

Un problema classico dell'informatica è ordinare delle code di dati che possiedono una data priorità. Questo tipo di problema viene risolto utilizzando liste concatenate o alberi binari (heap).

Line 64 ⟶ 65:

== Inserimento di un valore ==

Vediamo ora una rassegna dei principali metodi che sono associati ad una [[Codacoda di priorità|Priority queue]], 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>