Sommario della lezione · dinamici Deﬁnizione e costruzione della struttura dati H EAP...

Sommario della lezione

Introduzione alle strutture dati per la manipolazione di insiemi

dinamici

Definizione e costruzione della struttura dati HEAP

Applicazioni della struttura dati HEAP alla realizzazione di

Code a Prioritá

Applicazioni della struttura dati HEAP al problema

dell’ordinamento

Universita degli Studi di Salerno – Corso di Algoritmi – Prof. Ugo Vaccaro – Anno Acc. 2014/15 – p. 1/43

Strutture Dati

L’impiego di tecniche generali per il progetto di algoritmi (quali Divide etImpera, Programmazione Dinamica, Tecnica Greedy) ci ha permesso diottenere vari algoritmi efficienti per svariati problemi.

Tuttavia, l’uso delle sopracitate tecniche non garantisce, da solo, larealizzazione di algoritmi efficienti. Infatti:

l’uso intelligente di una struttuta dati scelta con accortezza é spesso unfattore cruciale per il progetto di algoritmi efficienti

• Ad es., solo la realizzazione di una struttura dati che supporti leoperazioni di inserimento ed estrazione dell’elemento di valore minimo dauna coda in tempo logaritmico garantisce che l’algoritmo greedy per lacostruzione di un albero di Huffman con n foglie abbia complessitáO(n log n)


Insiemi Dinamici e loro elementi

Molte algoritmi richiedono di manipolare insiemi la cui composizione puóvariare nel tempo (ad es. a causa di inserimenti di nuovi elementi, ocancellazioni di vecchi elementi, etc.)

Insiemi siffatti vengono chiamati Insiemi Dinamici.

“Tipiche” assunzioni sugli elementi di un insieme dinamico:• ciascun elemento é rappresentato da un oggetto i cui campi possonoessere manipolati ed esaminati se abbiamo un puntatore all’oggetto,• uno dei campi dell’oggetto é un campo chiave per la identificazionedell’oggetto,• i valori contenuti nel campo chiave si suppongono essere presi da uninsieme ordinato ,• l’oggetto puó anche contenere dei cosiddetti dati satelliti , memorizzatiin differenti campi dell’oggetto.


Operazioni possibili su insiemi dinamici

Le operazioni su insiemi dinamici possono essere raggruppati in duecategorie: operazioni di interrogazione , che ritornano informazioni circal’insieme, e operazioni di modifica , che cambiano l’insieme.


Operazioni che vedremo in questa lezione

• INSERT(S, x) : inserisce un elemento x nell’insieme S.

• MINIMUM(S) : ritorna l’elemento di S con la chiave di minimo valore.

• EXTRACT-MIN(S) : ritorna l’elemento di S con la chiave di minimo valoree lo cancella da S.

• DIMINUISCI-CHIAVE(S, x, k) : decrementa il valore della chiavedell’elemento puntato da x ad un nuovo valore k.

• AUMENTA-CHIAVE(S, x, k) : aumenta il valore della chiave dell’elementopuntato da x ad un nuovo valore k.

Strutture dati che supportano le operazioni di sopra sono dette(min)code a prioritá . Alternativamente, strutture dati che supportano leanaloghe operazioni di INSERT(S, x) , MAXIMUM(S) , EXTRACT-MAX(S) ,DIMINUISCI-CHIAVE(S, x, k) , e AUMENTA-CHIAVE(S, x, k) sono dette(max)code a prioritá .


(min)code a prioritá e (max)code a prioritá hanno molte applica zioni

Ad esempio, (max)code a prioritá hanno applicazioni nellaschedulazione di job in calcolatori.

In una tale situazione vi é una coda che mantiene traccia dei job ancorada eseguire da parte del calcolatore, e delle loro relative prioritá. Quandoun job é stato eseguito, oppure interrotto, il job con la prioritá massimaviene selezionato dalla coda con EXTRACT-MAX(S), ed eseguito dalcalcolatore. Ogni nuovo job che si presenta per essere eseguito potráessere inserito nella coda con INSERT(S, x). Le prioritá dei job possonoessere modificate con DIMINUISCI-CHIAVE(S, x, k) eAUMENTA-CHIAVE(S, x, k), se occorre.


(min)code a prioritá e (max)code a prioritá hanno molte applica zioni

(min)code a prioritá hanno applicazioni (oltre che nell’algoritmo diHuffman) in classi di applicazioni cosiddette “event-driven”.

In tali situazioni, ci sono dei compiti da eseguire (job da eseguire,pacchetti da leggere, ...) in un ordine crescente. Per vari motivi, talicompiti si possono presentare al loro “esecutore”, in tempi differenti ed inmaniera disordinata. L’esecutore puó usare una (min)code a prioritá perristabilire l’ordine di esecuzione, relativamente ai compiti nella coda,chiamando EXTRACT-MIN(S) per determinare qual é il nuovo compito daeseguire, ed appena se ne presenta un altro, con il suo relativo numerod’ordine, inserirlo nella coda con INSERT(S, x), usando il numero d’ordinecome chiave.

In questa lezione discuteremo di strutture dati per la implementazioneefficiente di (min)code a prioritá . Semplici modifiche a tali struttureforniranno implementazioni efficienti anche per (max)code a prioritá .


Implementazione di (min)code a prioritá mediante liste

La prima implementazione che potremmo realizzare é attraverso unasemplice lista a puntatori:

9 4 3 20 7 8 . . . . . . 15

Implementazione delle operazioni:

• INSERT(S, x) : inserisci l’elemento x alla testa della coda.

Complessitá: Θ(1)

• MINIMUM(S) : scorri tutta la coda e ritorna l’elemento con la chiave diminimo valore.Complessitá: Θ(n)


Implementazione di (min)code a prioritá mediante liste

• EXTRACT-MIN(S) : scorri tutta la coda, ritorna l’elemento con la chiavedi minimo valore, e cancellalo dalla coda.Complessitá: Θ(n)

• DELETE(S, x) : individua nella lista l’elemento puntato da x ed eliminalo.

Complessitá: Θ(1)

• DIMINUISCI-CHIAVE(S, x, k) : Individua l’elemento puntato da x, edecrementa il suo valore chiave a k.Complessitá: Θ(1)


Se invece usassimo un array ordinato

Implementazione delle operazioni:

• INSERT(S, x) : inserisci l’elemento x nell’array.

Complessitá: Θ(n)

• DELETE(S, x) : individua nell’array l’elemento x ed eliminalo.

Complessitá: Θ(n)

• MINIMUM(S) : ritorna l’elemento con la chiave di minimo valore.

Complessitá: Θ(1)

• EXTRACT-MIN(S) : ritorna l’elemento con la chiave di minimo valore, ecancellalo dall’array.

Complessitá: Θ(n)

• DIMINUISCI-CHIAVE(S, x, k) : individua l’elemento puntato da x, edecrementa il suo valore chiave a k.Complessitá: Θ(n)


Riassumendo...

Abbiamo le seguenti complessitá per la esecuzione di ciascunaoperazione:

Operazione Lista a puntatori Array ordinato

INSERT(S, x) Θ(1) Θ(n)

DELETE(S, x) Θ(1) Θ(n)

MINIMUM(S) Θ(n) Θ(1)

EXTRACT-MIN(S) Θ(n) Θ(n)

DIMINUISCI-CHIAVE(S, x, k) Θ(1) Θ(n)

La complessitá lineare di varie di esse é inaccettabile dal punto di vistapratico.


Implementazione mediante Heap

Definizione di Heap:

− Albero binario perfettamente bilanciato• l’ultimo livello puó essere incompleto (ma é riempito da sinistra

destra)− Per tutti i nodi v vale che key(v) ≥ key(parent(v))

Esempio:

25 3

9 19

15 14

11 4

23


Gli Heap possono essere memorizzati in (almeno) due modi:

1. Usando puntatori2. In un array, livello per livello da sinistra a destra

Esempio: 1

22

5

3

34

9

5

19

8

15

9

14

6

11

7

4

10

23

1 2 3 4 5 6 7 8 9 10

2 5 3 9 19 11 4 15 14 23

Notiamo che il figlio si-nistro del nodo mem-orizzato nell’entratai del vettore si trovanell’entrata 2i, ed il figliodestro nell’entrata 2i + 1.Analogamente, il padre sitrova nell’entrata ⌊i/2⌋


Proprietá degli Heap:

L’elemento di valore minimo é memorizzato nella radice, e l’altezza diuno heap con n nodi é Θ(log n)

Lo heap di altezza h che ha il massimo numero di nodi é fatto cosí

h

T1T2

Detto n il suo numero di nodi, é ovvio che

n = 1 + 2 + 4 + . . .+ 2h = 2h+1 − 1


Invece...

Lo heap di altezza h con il minimo numero di nodi é fatto cosí :

h

T1T2

h− 1

h− 2

Detto n il suo numero di nodi, é ovvio che

n = 1 + # nodi in T1 + # nodi in T2 = 1 + 2h−1 − 1 + 2h−1 − 1 + 1 = 2h

Di conseguenza, il numero di nodi n di un generico heap di altezza h

soddisfa 2h ≤ n ≤ 2h+1 − 1, ovvero (n+ 1)/2 ≤ 2h ≤ n, e quindi

h = Θ(logn)


Operazioni sullo heap

• INSERT(S, x) :

1. Inserisci x in una nuova foglia, piú a sinistra possibile nell’ultimolivello dell’albero.

2. Iterativamente, scambia di posizione elementi con il loro padre, finquando la proprietá di base dello heap ∀v key(v) ≥ key(parent(v))

non sia stata ristabilita


Esempio: inserimento di 4 nello heap

2

5 3

9 19

15 14

11 8

23

2

5 3

9 19

15 14

11 8

23 4

2

5 3

9 4

15 14

11 8

23 19

2

4 3

9 5

15 14

11 8

23 19


Operazione di I NSERT(S, x) in uno heap

La procedura prende in input il vettore A in cui é memorizzato lo heap, edil valore k = key[x] della chiave del nuovo elemento da inserire. Il campoheap-size[A] contiene il numero di elementi attualmente nello heap.Ricordiamo che per ogni nodo memorizzato in A[i], il suo padre nelloheap é memorizzato in A[Parent(i)], dove Parent(i) = ⌊i/2⌋

HEAP-INSERT(A, k)

1. heap-size[A]← heap-size[A] + 1

2. A[heap-size[A]]← k

3. while i > 1 AND A[Parent(i)] > A[i]

4. do scambia A[i]↔ A[Parent(i)]

5. i← Parent(i)

Complessitá: Il numero di volte che si cicla nel while é al piú pari allalunghezza del percorso foglia-radice nello heap, che sappiamo essereΘ(log n). Quindi, la complessitá di HEAP-INSERT(A, k) é Θ(log n).


L’operazione di E XTRACT-MIN(S) in uno heap:

• EXTRACT-MIN(S) :

1. Restituisci l’elemento che si trova nella radice dello heap;

2. Sostituisci l’elemento che si trova nella radice con quello che si trovanella foglia piú a destra del livello piú in basso dello heap;

3. Ripristina la proprietá dello heap: ∀v key(v) ≥ key(parent(v)), (se edove essa é stata violata), scambiando iterativamente un nodo con il figlioche ha il valore chiave minore.


Esempio di E XTRACT-MIN(S) in uno heap:

24 3

9 5

15 14

11 8

23 19

4 39 5

15 14

11 8

23 19

4 39 5

15 14

11 8

23 19

194 3

9 5

15 14

11 8

23

194 3

9 5

15 14

11 8

23

34 19

9 5

15 14

11 8

23

34 19

9 5

15 14

11 8

23

34 8

9 5

15 14

11 19

23


L’operazione di E XTRACT-MIN(S) in uno heap:

HEAP-EXTRACT-MIN(A)

1. return (A[1])

2. A[1]← A[heap-size[A]], heap-size[A]← heap-size[A]− 1

3. Min-Heapify(A, 1)

doveMin-Heapify(A, i)

1. ℓ← Left(i), r ← Right(i)

2. if ℓ ≤ heap-size[A]] AND A[ℓ] < A[i]

3. then smallest← ℓ

4. else smallest← i

5. if r ≤ heap-size[A] AND A[r] < A[smallest]

6. then smallest← r

7. if smallest 6= i

8. then scambia A[i]↔ A[smallest]

9. Min-Heapify(A, smallest)

Nelle linee 2-6 si troval’elemento minimo traA[i], A[ℓ], A[r]. Seesso é 6= da A[i], losi scambia con A[i] esi itera nel sottoalberocon la cui radice si éeffettuato lo scambio.


Complessitá di H EAP-EXTRACT-MIN(A, k)

Ogni chiamata a Min-Heapify(A, i) richiede un tempo costante.Chiamate successive a Min-Heapify(A, i) vengono effettuate su nodi idi livello sempre inferiore nell’albero, pertanto vengono effettuate al piúΘ(h) chiamate a Min-Heapify(A, i), dove h é l’altezza dello heap.Avendo mostrato in precedenza che h = Θ(log n), otteniamo che lacomplessitá di HEAP-EXTRACT-MIN(A, k) é Θ(logn).

É molto utile ricordare che la procedura Min-Heapify(A, i) é in gen-erale utilizzabile ogni qualvolta si voglia ripristinare in uno heap la pro-prietá di base dello heap: key(v) ≥ key(parent(v)) ∀v, eventualmenteviolata a causa di un cambiamento del solo valore di key(i).


Sulla procedura Min-Heapify(A, i)

É molto utile ricordare che la procedura Min-Heapify(A, i) é in generaleutilizzabile ogni qualvolta si voglia ripristinare in uno heap la proprietá dibase dello heap: key(v) ≥ key(parent(v)) ∀v, eventualmente violata acausa di un cambiamento del solo valore di key(i).

In altri termini, quando Min-Heapify(A, i) viene chiamata, si assumeche gli alberi binari radicati in Left(i) ed in Right(i) sia heap corretti, mache A[i] possa essere piú grande dei suoi figli, quindi violando laproprietá dello heap.

La funzione di Min-Heapify(A, i) é di scambiare l’elemento A[i] con ilminore dei suoi figli, e farlo successivamente “ scendere” nel sottoalberocorrispondente, fino a riprisitinare la proprietá dello heap.


Esempio: esecuzione di Min-Heapify(A, 2)

416 10

6 13

18 12

13 11

19

416 10

6 13

18 12

13 11

19

46 10

16 13

18 12

13 11

19

46 10

12 13

18 16

13 11

19


Ulteriori operazioni su heap

• MINIMUM(A) :

ritorna A[1].

• AUMENTA-CHIAVE(A, i, k) :

A[i]← k

Min-Heapify(A, i)

• DIMINUISCI-CHIAVE(A, i, k) :

1. A[i]← k

2. while i > 1 and A[Parent(i)] > A[i]

3. do scambia A[i]↔ A[Parent(i)]

4. i← Parent(i)


Esempio: esecuzione di D IMINUISCI-CHIAVE(A, 9, 5)

46 10

12 13

18 16

11 17

19

46 10

12 13

18 5

11 17

19

46 10

5 13

18 12

11 17

19

45 10

6 13

18 12

11 17

19


Riassumendo...

Abbiamo le seguenti complessitá per la esecuzione di ciascunaoperazione:

Operazione Lista Array Heap

INSERT(S, x) Θ(1) Θ(n) Θ(log n)

DELETE(S, x) Θ(1) Θ(n) Θ(log n)

MINIMUM(S) Θ(n) Θ(1) Θ(1)

EXTRACT-MIN(S) Θ(n) Θ(n) Θ(log n)

DIMINUISCI-CHIAVE(S, x, k) Θ(1) Θ(n) Θ(log n)

AUMENTA-CHIAVE(S, x, k) Θ(1) Θ(n) Θ(log n)


Applicazioni dello heap all’ordinamento

La struttura dati heap e le operazioni che essa supporta ci forniscono unsemplice algoritmo per l’ordinamento di un vettore A[1 . . . n] di n numeri

1. for i← 1 to n do

2. HEAP-INSERT(B,A[i]) %(costruiamo lo heap B mediante n ripetutiinserimenti degli elementi del vettore A)

3. for i← 1 to n do

4. A[i]← HEAP-EXTRACT-MIN(B) %(ordiniamo A mediante n

estrazioni di minimo dallo heap B)

Complessitá: L’istruzione 2. prende tempo O(log n), pertanto il for sullelinee 1. e 2. prende tempo O(n logn). L’istruzione 4. prende tempoO(log n), pertanto il for sulle linee 3. e 4. prende tempo O(n logn). Intotale, l’algoritmo prende tempo O(n log n) per ordinare n numeri.


É possibile migliorare il precedente algoritmo in due punti:

1. Nella costruzione dello heap (effettuandola quindi in tempo Θ(n))

2. Nella quantitá di memoria richiesta dall’algoritmo (in modo da nondover far uso di un vettore ausiliario).


Costruzione dello heap in tempo Θ(n)

L’idea é di usare la procedura Min-Heapify(A, i), iterativamemte inmaniera “bottom-up”, per trasformare un array A[1 . . . n] in uno heap.

Ricordiamo che quando Min-Heapify(A, i) viene chiamata, si assumeche gli alberi binari radicati in Left(i) ed in Right(i) siano heap corretti,ma che A[i] possa essere piú grande dei suoi figli, quindi violando laproprietá dello heap. Min-Heapify(A, i) scambia l’elemento A[i] con ilminore dei suoi figli, e fa successivamente “ scendere” A[i] nel sottoalberocorrispondente, fino a riprsitinare la proprietá dello heap.

L’osservazione di partenza é che tutti gli elelementi in A[⌊n/2⌋+ 1 . . . n]

sono foglie dell’albero binario che rappresenta l’array A (perché? Perchéper ciascuno di questi elementi A[i] vale Left(i) = 2i > n eRight(i) = 2i+ 1 > n, quindi essi non hanno figli nell’albero, ovvero sonofoglie). Dire che gli elementi in A[⌊n/2⌋+ 1 . . . n] sono foglie equivale adire che essi sono heap di taglia 1, quindi ecco gli heap di partenza percui applicare la procedura Min-Heapify(A, i).


Algoritmo di costruzione di heap

COSTRUISCI-MIN-HEAP(A)

1. heap− size[A]← lenght[A]

2. for i← ⌊length[A]/2] downto 13. do Min-Heapify(A, i)

Esempio: A = 16 19 17 18 4 11 10 6 12 13

16

1

2 3

19 174

18

5

48

6

9

12

6

11

7

1010

13

16

1

2 3

19 174

18

5

48

6

9

12

6

11

7

1010

13


continuazione dell’esempio C OSTRUISCI-MIN-HEAP(A)

16

1

2 3

19 174

18

5

48

6

9

12

6

11

7

1010

13

16

1

2 3

19 174

6

5

48

18

9

12

6

11

7

1010

13

16

1

2 3

19 104

6

5

48

18

9

12

6

17

7

1110

13

16

1

2 3

4 104

6

5

198

18

9

12

6

17

7

1110

13


continuazione dell’esempio C OSTRUISCI-MIN-HEAP(A)

16

1

2 3

4 104

6

5

138

18

9

12

6

17

7

1110

19

16

1

2 3

4 104

6

5

138

18

9

12

6

17

7

1110

19

4

1

2 3

16 104

6

5

138

18

9

12

6

17

7

1110

19

4

1

2 3

6 104

12

5

138

18

9

16

6

17

7

1110

19


Complessitá dell’algoritmo C OSTRUISCI-MIN-HEAP(A)

L’algoritmo COSTRUISCI-MIN-HEAP(A) richiede tempo Θ(n).

Prova. Sia T (k) il tempo impiegato, nel caso peggiore, daCOSTRUISCI-MIN-HEAP(A) per costruire uno heap di altezza k. Percostruire uno heap di altezza k, l’algoritmo COSTRUISCI-MIN-HEAP(A)

innanzitutto trasforma ciascuno dei due sottoalberi della radice in heap dialtezza al piú k − 1 (uno dei due potrebbe avere altezza k − 2). Ciórichiederá tempo ≤ 2T (k − 1). Successivamente, mediante la chiamata aMin-Heapify(A, 1), posiziona l’elemento A[1] nel posto che gli competenell’albero. Ció richiederá un tempo addizionale di Θ(k). Pertanto iltempo T (k) richiesto da COSTRUISCI-MIN-HEAP(A) soddisfa laequazione di ricorrenza

T (k) ≤ 2T (k − 1) + Θ(k).


Risoluzione dell’equazione T (k) ≤ 2T (k − 1) + Θ(k) per iterazione

T (k) ≤ 2T (k − 1) + Θ(k) ≤ 2(2T (k − 2) + Θ(k − 1)) + Θ(k)

= 22T (k − 2) + 2Θ(k − 1) + Θ(k)

≤ 22(2T (k − 3) + Θ(k − 2)) + 2Θ(k − 1) + Θ(k)

= 23T (k − 3) + 22Θ(k − 2) + 2Θ(k − 1) + Θ(k)

≤ . . . ≤ 2kT (0) + 2k−1Θ(1) + . . .+ 2Θ(k − 1) + Θ(k)

≤ a2k +k∑

i=1

2k−iΘ(i) ≤ a2k + bk∑

i=1

i2k−i

(per qualche costante a e b)

Sotto l’ipotesi che∑

k

i=1 i2k−i = Θ(2k), otteniamo T (k) = Θ(2k).

Ricordando che l’altezza k di uno heap di n nodi é k ≤ log n, otteniamoche la complessitá di COSTRUISCI-MIN-HEAP(A) é

T (log n) = Θ(2logn) = Θ(n)


Resta da provare che∑

k

i=1i2k−i = Θ(2k)

Osserviamo che∑k

i=1 i2k−i = 2k

∑k

i=1 i2−i ≤ 2k

∑∞

i=1 i2−i = 2k

∑∞

i=1 i(1/2)i (1).

Ricordiamo che, per valori x per cui |x| < 1 vale che

∞∑

i=0

xi =1

1− x(2).

Differenziando entrambi i membri della (2) otteniamo

d

dx

∞∑

i=0

xi =

∞∑

i=0

d

dxxi =

∞∑

i=0

ixi−1 =d

dx

1

1− x=

1

(1− x)2

da cui∑

∞

i=0 ixi = x/(1− x)2, ovvero, sostituendo x = 1/2, otteniamo∑

∞

i=1 i2−i = (1/2)/(1− (1/2))2 = 2. In conclusione

k∑

i=1

i2k−i ≤ 2k∞∑

i=1

i2−i = 2 · 2k = Θ(2k)


L’algoritmo H EAPSORT(A)

Il seguente algoritmo ordina un array A senza uso di un vettore ausiliario:

HEAPSORT(A)

1. COSTRUISCI-MIN-HEAP(A)

2. for i← lenght[A] downto 2

3. do scambia A[1]↔ A[i]

4. heap− size[A]← heap− size[A]− 1

5. Min-Heapify(A, 1)

L’algoritmo ordina gli elementi dell’array A nel verso dal piú grande al piúpiccolo, in tempo Θ(n logn) nel caso peggiore (infatti ognuna dellen = lenght[A] iterazioni del ciclo for prende al piú tempo Θ(log n) nel casopeggiore).


Esempio di esecuzione di H EAPSORT(A)

46 10

12 13

18 16

17 11

19

1

2 3

4 5 6 7

8 9 10

196 10

12 13

18 16

17 11

4

1

2 3

4 5 6 7

8 9 10

612 10

16 13

18 19

17 11

4

1

2 3

4 5 6 7

8 9 10

1912 10

16 13

18 6

17 11

4

1

2 3

4 5 6 7

8 9 10



1012 11

16 13

18 6

17 19

4

1

2 3

4 5 6 7

8 9 10

1812 11

16 13

10 6

17 19

4

1

2 3

4 5 6 7

8 9 10

1112 17

16 13

10 6

18 19

4

1

2 3

4 5 6 7

8 9 10

1912 17

16 13

10 6

18 11

4

1

2 3

4 5 6 7

8 9 10



1213 17

16 19

10 6

18 11

4

1

2 3

4 5 6 7

8 9 10

1813 17

16 19

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10

1316 17

18 19

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10

1916 17

18 13

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10



1618 17

19 13

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10

1918 17

16 13

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10

1718 19

16 13

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10

1918 17

16 13

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10



1819 17

16 13

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10

1918 17

16 13

10 6

12 11

4

1

2 3

4 5 6 7

8 9 10

E finalmente, otteniamo:

19 18 17 16 13 12 11 10 6 4


Avremmo potuto presentare la struttura dati MAX-HEAP, in cui vale laseguente proprietá:

− Per tutti i nodi v vale che key(v) ≤ key(parent(v))

La struttura dati MAX-HEAP puó essere utlizzata per implementare(max)code a prioritá (noi abbiamo visto heap per implementare(min)code a prioritá ) e, analogamente a quanto visto nella lezione, perordinare un array di numeri.La teoria sviluppabile per ottenere MAX-HEAP é perfettamenteequivalente a quella qui vista.


Sommario della lezione · dinamici Deﬁnizione e costruzione della struttura dati H EAP...

Documents

Transcript of Sommario della lezione · dinamici Deﬁnizione e costruzione della struttura dati H EAP...