Esercizio
SiaS = S [1], S [2], . . . , S [n]una sequenza dinentry con chiavi intere distinte (ad es., film con i loro rating), e siaτ un intero in[1, n]. Si vuole progettare un algoritmo che trovi leτ entry inS con chiave maggiore (Top-τ entry) basato sul seguente schema.
Algoritmo Top(S,τ)
Input: SequenzaS dinentry, interoτ ≤ n Output: τ entry diS con chiave pi`u grande Q←−priority queue vuota;
fori ← 1tondo
if (i ≤ τ) thenQ.insert(S [i ].getKey(),S [i ].getValue()); else
returnQ
1 Completare l’algoritmo in modo che sia corretto e cheQ non contegna mai pi`u diτ entry.
2 Provare la correttezza dell’algoritmo usando un opportuno invariante per il ciclo for.
3 Analizzare la complessit`a assumendo di implementareQ tramite Heap su array.
Esercizio (C-9.36 [GTG14])
SianoT1eT2due alberi binari (non necessariamente completi e
implementati tramite struttura linkata) i cui nodi memorizzano delle entry in modo da soddisfare la heap-order property. Descrivere un algoritmo per combinareT1eT2in un unico albero binarioT i cui nodi
contengano tutte le entry diT1eT2, mantenendo la heap-order property.
La complessit`a dell’algoritmo deve essereO (h1+ h2), doveh1eh2
rappresentano le altezze diT1 eT2, rispettivamente.
Esercizio
SiaS = S [1], S [2], . . . , S [n]una sequenza contenentenchiavi distinte e siamun indice intero tale che1 ≤ m ≤ n/ log2n. Progettare un algoritmo che in tempoO (n)determini lam-esima chiave pi`u piccola di S. (Analizzare la complessit`a dell’algoritmo per far vedere che `eO (n).)
