Heap binario: differenze tra le versioni

Versione delle 10:36, 5 lug 2021

Versione attuale delle 19:53, 2 feb 2025

(7 versioni intermedie di 4 utenti non mostrate)

Riga 1:

{{F|programmazione|febbraio 2013}}

[[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'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 14:

Nell'immagine in alto a destra è possibile osservare quanto descritto, in aggiunta si può dire che viene definito come ''last'' (ultimo) l'elemento che si trova più a destra nel livello delle foglie. Nell'esempio last ha valore 15. Questo particolare nodo assume un compito determinante nei metodi per la rimozione della chiave minima (che è ovvio supporre, per le proprietà citate, si trovi nella radice) e nell'inserimento di una nuova chiave.

== DefinizioneOperazioni sullo heap ==

Sia <math>U</math> un insieme di elementi e <math>P</math> un insieme totalmente ordinato.

Un Heap di elementi appartenenti ad <math>U</math> è un elemento di <math>U^*</math> che supporta le operazioni di:

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>

Line 92 ⟶ 93:

== Altri progetti ==

{{Interprogetto|preposizione=sull'}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{strutture dati}}