HeapOrdinamento e code di priorità

Ugo de’ Liguoro

Heap: definizione

Definizione. Uno Heap (binario) è un albero binario finito i cui vertici sono etichettati da elementi di un insieme linearmente ordinato (chiavi), che soddisfa:

1. Se v è figlio di v’ allora chiave(v) chiave(v’);

2. L’albero è completo salvo al più l’ultimo livello, che è riempito da

sinistra.

Uno heap binario può essere realizzato come un vettore H di dimensione pari alla cardinalità dell’albero e tale che:

• H[1] sia la radice dell’albero

• H[2i] e H[2i+1] siano rispettivamente il figlio sinistro e quello destro di H[i].

Ne segue che l’elemento la cui etichetta è maggiore tra tutte quelle dei vertici dell’albero, è la radice ossia H[1].

Heap: esempio

16

9 14

7 4 8 10

3 2 1

16 9 14 7 4 8 10 3 2 1

1 2 3 4 5 6 7 8 9 10

H =

Left, Right, ParentPer muoversi all’interno di uno heap rappresentato come un vettore sono utili le seguenti funzioni:

// fissato uno heap h e la sua dimensione HeapSize(h)

Parent(i) = i / 2 // se i 0

Left(i) = if 2i < HeapSize(h) then 2i else i

Right(i) = if 2i+1 < HeapSize(h) then 2i+1 else i

InserimentoPer inserire un nuovo elemento in uno heap, Insert lo aggiunge come foglia dell’albero; quindi la fa risalire lungo il ramo cui è stato aggiunto sinché non sia ricostruito lo heap.

Insert (h: heap; x: key)

HeapSize(h) := HeapSize(h)+1

i := HeapSize(h)

h[i] = x

while i > 1 and h[Parent(i)] < h[i] do

exchange(h[i], h[Parent(i)])

i := Parent(i)

Nota: la complessità è dell’ordine della lunghezza del ramo ossia O(log n)

Heap: Inserimento (1)

16

9 14

7 4 8 10

3 2 1 15

Heap: Inserimento (2)

16

9 14

7

4

8 10

3 2 1

15

Heap: Inserimento (3)

16

9

14

7

4

8 10

3 2 1

15

Heap: Inserimento (4)

16

9

14

7

4

8 10

3 2 1

15

EstrazioneL’estrazione da uno heap avviene dalla radice. Consta di due fasi:

1) l’elemento più a destra dell’ultimo livello rimpiazza la radice;

2) l’elemento ora in radice viene fatto discendere lungo l’albero finché non sia maggiore di entrambi i figli; nel discendere si sceglie sempre il figlio col valore massimo della chiave.

ExtractMaximum (h: heap)

h[1] := h[HeapSize(h)]

HeapSize(h) := HeapSize(h) - 1

Heapify(h,1) // Fase (2)

Fase (1)

Heapify (h: heap; i: index)

largest := index of max{h[i],h[Left(i)],h[Right(i)]}

if largest i then

exchange(h[i],h[largest])

Heapify(h,largest)

La fase (2), di cui si incarica Heapify, è più generale, poiché questa funzione può iniziare il suo lavoro in qualunque punto i dello heap, purché i sottoalberi con radice in Left(i) e Right(i) siano a loro volta degli heap:

Ricostruzione di uno heap

Nota: se n è la cardinalità dell’albero con radice in i, allora Heapify è O(log n) (caso peggiore).

Heap: Estrazione (1)

16

9

14

7

4

8 10

3 2 1

15

Heap: Estrazione (2)

4

9

14

7 8 10

3 2 1

15

Heap: Estrazione (3)

4

9

14

7 8 10

3 2 1

15

Heap: Estrazione (4)

4

9 14

7 8 10

3 2 1

15

Heap: Estrazione (5)

4

9 14

7 8 10

3 2 1

15

Usi di uno heap

La struttura heap può essere impiegata per:

• implementare code di priorità;

• realizzare un algoritmo di ordinamento ottimo, HeapSort.

Code di priorità (ADT)Una coda di priorità è un insieme finito S di oggetti su cui è definita una funzione priorità: S Nat. Le operazioni definite su di essa sono illustrate nella seguente specfica ADT:

datatype PriorityQueue, Element;

constructors: EmptyQueue: PriorityQueue

Insert: PriorityQueue, Element -> PriorityQueue

ExtractMaximum: PriorityQueue -> PriorityQueue

observations:

Maximum: PriorityQueue -> Element

semantics:

Insert(S,x) = S {x}

Maximum(S) = x tale che Priorità(x) =

max {Priorità(y)| y S}

ExtractMaximum(S) = S \ {Maximum(S)}

Code di priorità: implementazione

Si possono implementare con gli heap: la funzione priorità si implementa codificando ogni elemento come una coppia elemento, priorità (usando le strutture del C), e strutturando lo heap in base alla seconda coordinata di ciascuna coppia (la chiave).

Le funzioni Insert e ExtractMaximum sono quelle viste; la funzione Maximum è semplicemente:

Maximum (h: heap)

return h[1] // il massimo è sempre in radice

La funzione, non essendo distruttiva, non richiede infatti alcuna ricostruzione dello heap, ed ha complessità O(1).

Heapsort (1)Si può sfruttare la struttura dati heap per costruire un algoritmo di ordinamento simile, per struttura, al SelectSort con selezione del massimo.

iV

1 n

V[1..i] è uno heap V[i+1..n] è ordinato

x V[1..i] y V[i+1..n]. x y

HeapSort(v: array)

BuildHeap(v) // riorganizza v in uno heap

for i := Length(v) downto 2 do

exchange(v[1],v[i])

HeapSize(v) := HeapSize(v) - 1

Heapify(v,1)

HeapSort (2)BuildHeap. Se v[1..n] è un vettore qualsiasi, BuildHeap(v) lo riorganizza in modo che sia uno heap. Pensando h[n/2 +1 .. n] come le foglie dell’albero che diventerà uno heap, la condizione che Left(n/2 +1 ) e Right(n/2 +1 ) siano heap è trivialmente soddisfatta, onde possiamo iterare Heapify da n/2 a 1:

BuildHeap(v: array)

for i := length(v)/2 downto 1 do

Heapify(v,i)

Nota: un confine superiore alla complessità di BuildHeap è O(n log n) (si itera una procedura O(log n) per ciascuno degli n vertici). Questa stima grossolana si può raffinare sino a mostrare che in realtà BuildHeap è lineare.

Heapsort (3)A differenza del SelctSort, che è O(n2), HeapSort ha complessità O(n log n), quindi è un algoritmo ottimo per l’ordinamento. Ciò si deve all’efficienza della selezione del massimo nel semivettore sinistro, che ha complessità logaritmica:

HeapSort(v: array)

BuildHeap(v) // O(n log n) (o meglio O(n))

for i := Length(v) downto 2 do // O(n) cicli

exchange(v[1],v[i])

HeapSize(v) := HeapSize(v) - 1

Heapify(v,1) // O(log n)

Allora: O(n) + O(n) O(log n) = O(n) + O(n log n) = O(n log n).

Heap: fine.