Gli Heap
Uno heap è un albero binario quasi completo i cui nodi contengono dei dati, ciascuno cartterizzato da un campo chiave, che soddisfa le seguenti proprietà:
- tutte le foglie dello heap hanno profondità h o h-1
- le foglie di profondità h-1 (se ce ne sono) stanno "a destra" delle foglie di profondità h
- tutti i nodi interni hanno grado 2, eccetto al più uno
- ogni nodo soddisfa la "heap property":
- min-heap la chiave dei nodi è <= della chiave dei figli: key[ p[i] ] <= key[i]
l'elemento con chiave minore è memorizzato nella radice - max-heap la chiave dei nodi è >= della chiave dei figli: key[ p[i] ] >= key[i]
l'elemento con chiave maggiore è memorizzato nella radice
C'è un'orinamento parziale sulle chiavi dei nodi.
Poichè lo heap è un albero binario quasi completo, se il numero di nodi è pari a
n, la sua altezza sarà
O( log2n )Rappresentazione mediante un vettore
- la radice viene memorizzata nell'elemento di indice 1 (il primo del vettore)
- i 2 figli dell'elemento in posizione i vengono memorizzati negli elementi in posizione
- 2i figlio sinistro
- 2i + 1 figlio destro
Dal momento che lo heap è un albero binario quasi completo, l'indice
i di tutti i suoi elementi nel vettore rispettano l'espressione
i<=n
- i < n >> 1 il nodo i ha 2 figli
- i = n >> 1 il nodo i ha uno (n pari) o due (n dispari) figli
- i > n >> 1 il nodo i è una foglia
NB: l'array da sinistra a destra rappresenta la visita in ampiezza dell'albero
Costruzione di uno heap
Si utilizza come base la
Heapify(X, i), i cui paramentri sono il vettore
X ed un indice
i al suo interno.
La procedura presuppone che:
- i 2 sottoalberi corrispondendi ai figli dell'elemento memorizzato in i siano degli heap
- l'elemento in i possa avere valore minore (maggiore) di quello dei figli.
La
Heapify provvederà quindi ha ripristinare la proprietà di Heap nel sottoalbero radicato in
i:
- gli alberi binari con radici left[i] e right[i] sono max-heap (min-heap)
- ma l'albero binario radicato in i non è un max-heap (min-heap).
Verrà quindi ripristinata la proprietà di max-heap (min-heap) sul sottoalbero con radice
i facendo "scendere" l'elemento
A[i] nell'array.
Heapify(X[], i)
l <-- left[i]
r <-- right[i]
if ( l <= n and X[l] > X[i] )
largest <-- l
else
largest <-- i
if (r <= n and X[r] > X[largest] )
largest <-- r
if ( largest != i )
swap( X[i], X[largest] )
Heapify(X, largest)
|
Complessità:
O( log2n )Build-heap
Utilizza la procedura
Heapify per trasformare un albero binario (memorizzato in un vettore) in uno heap.
Consiste nell'applicare
Heapify sugli elementi nella prima metà del vettore
Build-Heap(X[])
for i <-- n>>1 downto 1
Heapify(X,i)
|
Complessità:
O( n )
Heapsort
Algoritmo di ordinamento iterativo and in-place che sfrutta le proprietà degli heap e le operazioni su di esse definite
- Build-Heap sul vettore: trasforma i vettore di un heap
- Scambia il primo elemento (la radice contiene il valore max) con l'ultimo
- Riduce la dimensione dello heap di 1
- Ripete da 1
Heapsort(X[])
Build-Heap(X)
for i <-- lenght(X) downto 2
swap( X[1], X[i] )
heap-size[X] <-- heap-size[X] -1
Heapify(X, 1)
|
Complessità:
O( n log2n)
Coda con priorità
Struttura dati su cui sono definite le seguenti operazioni
- insert(S, x) O( log2 n )
Inserisce l'elemento x nell'insieme S
Normale inserimento in uno heap
- maximum(S) O( 1 )
restituisce l'elemento di S con chiave massima
Restituisce l'elemento radice
- extract-maxmimum(S, &x) O( log2 n )
restituisce e rimuove da S l'elemento con chiave massima
Restituisce l'elemento radice e lo elimina dallo heap
Heap-Insert(S, x)
heap-size[S] <-- heap-size[S] + 1
i <-- heap-size[S]
while ( i>1 and S[ p[i] ] < x )
S[i] <-- S[ p[i] ]
i <-- p[i]
S[i] <-- x | Heap-Exstract-Max(S)
if ( heap-size[S] < 1)
error "underflow"
max <-- S[1]
S[1] <-- S[ heapsize[S] ]
heapsize[S] <-- heapsize[S] - 1
Heapify(S, 1)
return max
|