- ...potenziale1
- per
si intenderà in seguito il
potenziale associato allo stato della struttura
dopo l'
-esima operazione.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... costante2
- In tabella è
riportata anche la complessità reale nel caso pessimo.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... 3
- Per
si intende il numero di radici contenute nella lista dello heap
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... heap4
- Per ogni nodo vale che il padre
ha chiave minore di ciascun figlio; in questo modo é anche garantito che il
nodo con chiave minima dello heap è sicuramente la radice di un albero.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... intero5
- non è necessario che il campo chiave sia di tipo intero,
ma è sufficiente che faccia parte di un insieme che goda della proprietà di
ordinamento totale!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... archi6
- si ricorda che un arco non è altro che la
tripla (nodo, nodo, peso)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ... ``inutili''7
- Per arco inutile si intende
l'arco che collega due nodi già appartenenti a T. La presenza di
archi ``inutili'' è dovuta al fatto che in un dato momento
possono essere presenti in I più archi comprendenti un dato
nodo; quando tale nodo viene inserito in T, da I viene estratto
un solo di questi archi mentre i restanti diventano per l'appunto
``inutili''.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.