Code a priorità (Heap)
Definizione
Heapify (mantenimento coda a priorità)
Costruire un Heap
Insert, Maximum e Extract-Max
Coda a priorità (Heap)
• Una coda a priorità può essere rappresentato da
un albero binario completo.
• La chiave del padre è sempre maggiore di
quella dei figli: key(i) ≤ key(parent(i)) .
Albero binario completo:
16
Sono riempiti tutti i livelli eccetto
possibilmente l’ultimo. Altezza=Θ(log(n))
Coda a priorità:
10
14
Il nodo a maggiore priorità (con la chiave
8
più grande) sta in cima.
Nota: si può ragionare in maniera
analoga quando si pone che
key(i) ≥ key(parent(i)).
2
7
4
1
9
3
Heap tramite un Array
• Una coda a priorità può essere implementato tramite
1
un’array (A).
16
A[PARENT(i)] ≥ A[i].
3
2
PARENT(j)
1.
return  j/2 
4
8
A
3
5
6
7
8
9
16 14 10 8
7
9
3
2 4 1
9
10
4
1
length[A]
heap-size[A]
4
7
6
7
9
2
RIGHT(i)
1.
return 2i+1
2
5
8
LEFT(i)
1.
return 2i
1
10
14
n
10
…
3
Heapify
(mantenimento coda a priorità)
• Si sistema l’elemento A[i]: si suppone gli alberi
con radice LEFT(i) e RIGHT(i) siano degli Heap.
LEFT[i]
HEAP
A[i]
RIGHT[i]
HEAP
Heapify
(mantenimento coda a priorità)
• Si sistema l’elemento A[i]: si suppone gli alberi
con radice LEFT(i) e RIGHT(i) siano degli Heap.
HEAPIFY(A,i)
// sistema A[i] nel Heap
1.
l ← LEFT(i)
// figlio sx
2.
r ← RIGHT(i)
// figlio dx
3.
if l ≤ heap-size[A] and A[l] > A[i] // cerca il maggiore fra padre e
4.
then magg ← l
// i due figli (se ci sono…)
5.
else magg ← i
6.
if r ≤ heap-size[A] and A[r] > A[magg]
7.
then magg ← r
8.
if magg ≠ i
// il magg è uno dei due figli…
9.
then scambia A[i] ↔ A[magg]
10.
HEAPIFY(A,magg)
Esempio Heapify
• All’inizio si chiama HEAPIFY(A,2)
1
1
16
16
3
2
4
5
7
9
2
4
1
5
9
2
7
10
8
7
6
i
4
3
8
10
8
9
10
14
7
6
14
8
10
i
4
3
2
1
9
3
Esempio Heapify
• Il costo in termine di tempo è nel caso peggio
l’altezza dell’albero. O(h) = O(log(n))
1
16
3
2
10
14
4
5
8
8
7
i
9
2
4
7
6
10
1
9
3
Costruire l’Heap
BUILD-HEAP(A)
// strategia bottom-up: dal basso verso l’alto
1.
heap-size[A] ← length[A]
//
2.
for i ← length[A]/2 downto 1
// dalla metà in su
3.
do HEAPIFY(A,i)
// sotto la metà sono tutte foglie
• Il costo di HEAPIFY è O(log(n)) e viene
chiamato O(n) volte. Quindi un limite del caso
peggiore è O(n log(n)).
• In realtà, il caso peggiore può essere stimato
come O(n).
=2
logn 

h 0

logn  h
h
 n 
 2h1 O(h)  O(n  2h1 )  O(n 2h1 )  O(2n)  O(n)
h 0
h 0
Rappresenta il massimo numero di sottoalberi pieni
ad altezza h (avendo a disposizione n elementi)
Esempio costruzione Heap
1
A
5
6
7
8
9
10
2
3
4
4 1
3
2 16 9 10 14 8 7
Si
comincia
da qua
Foglie
1
1
4
4
3
2
3
1
4
5
8
9
14
4
7
5
i
2
10
8
10
8
9
3
1
7
6
i 16
2
3
2
9
14
16
10
8
7
6
7
9
10
Esempio costruzione Heap
Strategia button-up: dal basso verso l’alto si chiama
HEAPIFY su tutte i nodi interni.
1
1
4
4
3
2
3 i
1
4
5
14
8
2
4
7
5
14
10
8
10
8
9
10
8
7
6
16
9
2
10
i
1
7
6
16
9
3
2
7
9
3
Esempio costruzione Heap
Strategia button-up: dal basso verso l’alto si chiama
HEAPIFY su tutte i nodi interni.
1
1
i
4
16
3
2
3
16
4
5
7
9
2
4
1
5
7
9
2
10
4
7
6
8
10
8
10
8
9
10
14
7
6
14
8
3
2
1
9
3
Altre operazioni
• MAXIMUM(A): ritorna l’elemento a
massima priorità, ossia quello in cima.
• EXTRACT-MAX(A): estrae l’elemento a
massima priorità, successivamente l’Heap
andrebbe sistemato
• INSERT(A): inserisce un nuovo elemento
nel Heap.
MAXIMUM e EXTRACT-MAX
MAXIMUM(A) ha un tempo di esecuzione
costante, O(1)
MAXIMUM(A)
1.
return A[1]
// restituisci l’elem. a magg. priorità,
// ossia quello in cima
EXTRACT-MAX(A) ha un tempo di esecuzione
O(log(n)), dovuto alla chiamata HEAPIFY().
EXTRACT-MAX(A)
// Estrae elemento a maggiore priorità
1.
if heap-size[A] < 1
// heap vuoto?
2.
then error “heap underflow”
3.
max← A[1]
// memorizza elem. In cima
4.
A[1]← A[heap-size[A]]
// metti l’ultimo elemento in cima
5.
heap-size[A]← heap-size[A] – 1
// heap diminuisce di 1 elem.
6.
HEAPIFY(A,1)
// HEAPIFY sul 1° elem.
7.
return max
// restituisci l’elem. a magg. priorità
HEAP-INSERT
HEAP-INSERT(A, KEY) ha un tempo di
esecuzione O(log(n)), nel caso peggiore si
risale l’albero dalla foglia alla radice.
HEAP-INSERT(A, key)
// Inserisci elemento nell’Heap
1.
heap-size[A]← heap-size[A] + 1
// aumenta Heap di 1 elemento
2.
i← heap-size[A]
// inizia dall’elem. inserito (ultimo)
3.
while i > 1 and A[PARENT(i)]<key // il nuovo elem. Viene fatto
4.
do A[i] ← A[PARENT(i)]
// risalire…
5.
i← PARENT(i)
6.
A[i] ← key
// fino a trovare il suo posto
Inserimento in un Heap
HEAP-INSERT(A, 15)
key=15
L’Heap viene aumentato di un elemento.
Si procede poi a risalire l’albero per trovare il suo posto.
1
1
16
16
3
2
3
14
4
5
7
9
2
4
10
8
11
10
4
9
1
8
10
14
7
6
8
8
3
2
i
Nuovo elemento
key = 15
2
5
8
i
9
10
4
7
6
7
9
11
1
7
3
Inserimento in un Heap
HEAP-INSERT(A, 15)
key=15
L’Heap viene aumentato di un elemento.
Si procede poi a risalire l’albero per trovare il suo posto.
1
1
16
16
3
2
4
5
8
8
1
4
7
5
8
10
8
11
10
4
9
10
15
7
6
14
9
2
3
i
14
3
2
14
9
2
9
11
10
4
7
6
1
7
3
Considerazioni
• La struttura dati Heap gestisce una coda a
priorità.
• Viene estratto l’elemento a maggiore priorità
(es. quello con chiave maggiore)
• Si può invertire la relazione con il padre, se
key(i) ≥ key(parent(i)).
– In questo caso l’elemento a maggiore priorità è
l’elemento più piccolo
• Heap-sort: algoritmo di ordinamento che usa un
Heap. Si estrae ogni volta l’elemento più piccolo
fino ad ottenere un vettore ordinato.
Tempo O(n log(n)).