Heap binario: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 61:
<math>\sum_{i=1}^k 2 i 2 ^ {k - i}</math>
== Inserimento di un valore ==
Vediamo ora una rassegna dei principali metodi che sono associati ad una [[coda con priorita'|Priority queue]], ovvero una struttura dati in cui in ogni momento è possibile associare una priorita' alle entry che ne fanno parte.
Riga 78:
nell'algoritmo appare una tecnica di scorrimento dell'heap chiamata '''up-heap bubbling''', ovvero, dato un indice ''i'' nell'array, si controlla se le proprieta' dell'albero sono verificate per ''i'' e per il suo padre, definito come la parte bassa di ''i/2''.
== Cancellazione della radice ==
Un'operazione classica di una struttura heap è la cancellazione della radice. Quest'operazione può comportare problemi a mantenere la struttura heap. Il metodo più semplice è quello di sostituire la radice cancellata con il valore minore dell'heap, logicamente l'ultimo valore dell'array associato all'heap oppure il valore più a destra nell'ultimo livello dell'albero completo. A questo punto si effettua il ripristino della struttura di heap tramite confronti e scambi.
[[Categoria:Strutture dati]]
| |||