Heap binario: differenze tra le versioni

Versione delle 01:27, 16 lug 2020

Versione delle 01:21, 8 apr 2021

Riga 1:

{{F|programmazione|febbraio 2013}}

[[File:HeapVector.PNG|thumb|Implementazione di un heap (min-heap) mediante Vettore]]

UnUno '''heap binario''', è ununo [[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'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.

*Condizione di forma: tutti i livelli dell'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 12:

Sia '''U''' un insieme di elementi e '''P''' un insieme totalmente ordinato.

Un Heap di elementi appartenenti ad '''U''' è un elemento di '''U*''' che supporta le operazioni di:

*Inserimento: inserisci <math> U^* \times U \times P </math>, <math>inserisci (H, e, p)</math>, inserisce nell'nello heap H, l'elemento e con priorità p, dopo l'inserimento l'insieme mantiene le proprietà dell'dello heap.

*Rimozione

*Lettura