Algoritmi e Strutture Dati con domande riassuntive

HEAPSORT(H)

BUILDHEAP(H)

for i=1 to n

Scambia(H,1, heapsize(H))

heapsize(H)--

HEAPIFY(H,1)

Tempo:

HEAPSORT ha un tempo di esecuzione di O(n log n), in quanto BUILDHEAP impiega O(n) e

​

ciascuna delle n chiamate impiega O(log n).

Code di priorità

Heapsort è un eccellente algoritmo, ma Quicksort è ancora più veloce. Nonostante ciò, la

struttura dati Heap è molto utile con le code di priorità.

Esistono due tipi di code di priorità:

● code di max-priorità​ , basate sul max-heap

​

● code di min-priorità, basate sul min-heap

​ ​

Definizione: una coda di priorità è una struttura dati che serve a mantenere un insieme S

​

di elementi, ciascuno con valore associato detto c

hiave​

.

​ ​

Operazioni max-priorità: Una coda di m

ax​ priorità supporta le seguenti operazioni:

​ ​ S x

● INSERT(S,x), inserisce elemento x nell’insieme S

. Può essere scritta ← { }

⋃

​

● MAXIMUM(S) restuituisce l’elemento di S con la chiave più grande.

​

● EXTRACT-MAX(S) elimina e restituisce l’elemento di S con la chiave più grande.

​

● INCREASE-KEY(S,x,k) aumenta il valore della chiave dell’elemento x al nuovo valore

​

k, che si suppone sia almeno pari al valore corrente della chiave dell’elemento x

.

Applicazioni possibili max-priorità: Le code di max-priorità possono essere utilizzate per

programmare i compiti su un computer condiviso. La coda di max-priorità tiene traccia dei

compiti da svolegere e delle loro relative priorità. Quando un compito è ultimato o interrotto,

viene selezionato il compito con priorità più alta tra quelli in attesa mediante

EXTRACT-MAX. Un nuovo compito può essere aggiunto alla lista in ogni momento tramite

INSERT.

Operazioni min-priorità:

● INSERT

● MINIMUM

● EXTRACT-MIN

● DECREASE-KEY

Applicazioni possibili min-priorità: una coda di min-priorità può essere utilizzata in un

simulatore controllato da eventi e gli elementi della coda sono gli eventi da simulare. Ogni

elemento della coda è associato al tempo in cui l’evento si può verificare; questo tempo

serve da chiave dell’evento. Gli eventi devono essere simulati secondo l’ordine dei loro

tempi, in quanto la simulazione di un evento può causare la simulazione di eventi futuri.

Il programma di simulazione usa EXTRACT-MIN a ogni passaggio per selezionare il

successivo evento da simulare.

Ogni volta che viene prodotto un nuovo evento, INSERT lo inserisce nella coda.

Handle: come detto prima, si può utilizzare un heap per implementare una coda di priorità.

In un’applicazione, come la programmazione dei compiti o la simulazione degli eventi, gli

elementi di una coda di priorità corrispondono agli oggetti dell’applicazione. Spesso è

necessario determinare quale oggetto dell’applicazione corrisponde a un dato elemento della

coda di priorità e viceversa.

Quindi, quando un heap viene utilizzato per implementare una coda di priorità, spesso

​ ​

occorre memorizzare un handle (aggancio) con il corrispondente oggetto dell’applicazione in

ogni elemento dell’heap. Bisogna però memorizzare un handle che faccia il percorso

inverso, dal corrispondente elemento dell’heap in ogni oggetto dell’applicazione. Qui,

tipicamente, l’handle è un indice dell’array.

Poichè gli elementi dell’heap cambiano posizione nell’array durante le operazioni, è

necessario aggiornare l’indice dell’array nel corrispondente oggetto dell’aplicazione.

HEAP-MAXIMUM:

HEAP-MAXIMUM(A)

return A[1]

Tempo Θ(1) ​

HEAP-EXTRACT-MAX (simile al ciclo for della procedura HEAPSORT)

HEAP-EXTRACT-MAX(A)

if heapsize[A] < 1

error “underflow dell’heap”

max = A[1]

A[1] = A[heapsize[A]]

heapsize[A] = heapsize[A]-1

HEAPIFY(A,1)

return max

Tempo O(log n), in quanto svolge soltanto una quantità costante di lavoro oltre al tempo

O(log n) di HEAPIFY.

HEAP-INCREASE-KEY

● Implementa l’operazione INCREASE-KEY

● L’elemento della coda di priorità la cui chiave deve essere aumentata è identificato

​

da un indice i nell’array.

● L’algoritmo aggiorna la chiave dell’elemento A[i] con il suo nuovo valore

● Poichè l’incremento della chiave potrebbe violare la proprietà dell’heap, l’algoritmo, in

una maniera che ricorda il ciclo di inserzione di INSERTION-SORT, segue un

percorso da questo nodo verso la radice per trovare un posto appropriato alla nuova

chiave.

● Durante questo percorso, confronta ripetutamente un elemento con suo padre e, se

la chiave dell’elemento è più grande, scambia le loro chiavi. Questa operazione

termina se la chiave del padre è più grande di quella dell’elemento.

HEAP-INCREASE-KEY(A, i, chiave)

if chiave < A[i]

error “la nuova chiave è più piccola di quella corrente”

A[i] = chiave

while i > 1 and A[PARENT(i)] < A[i]

scambia A[i] <-> A[PARENT(i)]

i = PARENT(i) ​ ​

Tempo esecuzione: con un heap di n elementi è O(log n), in quanto il cammino seguito dal

nodo aggiornato alla riga 3 alla radice ha lunghezza O(log n).

MAX-HEAP-INSERT

● Implementa l’opzione INSERT. ​

● Prende come input la chiave del nuovo elemento da inserire nello heap A

.

● La procedura prima espande lo heap aggiungendo all’albero una nuova foglia con

chiave -∞

● Poi chiama HEAP-INCREASE-KEY per impostare la chiave del nuovo elemento al

suo valore corretto e mantenere la proprietà dello heap.

MAX-HEAP-INSERT(A, chiave)

heapsize[A] = heap-size[A]+1

A[heapsize[A]] = -∞

HEAP-INCREASE-KEY(A, heapsize[A], chiave)

​

Tempo esecuzione:​ con un heap di n elementi è O(log n).

Un heap può svolgere qualsiasi operazione con le code di priorità su un insieme di

​

dimensione n nel tempo O(log n)

Hashing

● Una tabella hash è una struttura dati efficace per implementare i dizionari.

● Sebbene la ricerca di un elemento in una tabella hash possa richiedere lo stesso

tempo per ricercare un elemento in una lista concatenata (Θ(n) nel caso peggiore) in

pratica l’hashing ha ottime prestazioni. Il tempo atteso per cercare un elemento in

una tabella hash è O(1)

Indirizzamento diretto

● è una tecnica semplice che funziona bene quando l’universo U delle chiavi è

ragionevolmente piccolo.

● Supponiamo che un’applicazione abbia bisogno di un insieme dinamico in cui ogni

​

elemento ha una chiave estratta dall’universo U = {0,1...m-1} dove m non è troppo

grande. Supponiamo inoltre che due elementi non possano avere la stessa chiave

​

● Per rappresentare l’insieme dinamico si utilizza un array o una tabella a

​ ​

indirizzamento diretto​ , indicata con T=[0...m-1] dove ogni posizione o slot

corrisponde ad una chiave dell’universo U.

● Funzionamento

​ ​

○ Lo slot k punta a un elemento dell’insieme con chiave k

. Se l’insieme non

​

contiene l’elemento con chiave k

, allora T[k] = NIL.

DIRECT-ADDRESS-SEARCH(T, k)

return T[k]

DIRECT-ADDRESS-INSERT(T, x)

T[key[x]] = x

DIRECT-ADDRESS-DELETE(T, x)

T[key[x]] = NIL ​

Tempi esecuzione: O(1)

Per alcune applicazioni, gli elementi dell’insieme dinamico possono essere memorizzati nella

stessa tabella a indirizzamento diretto. Ovvero, anzichè memorizzare la chiave e i dati satelli

di un elemento in oggetto esterno alla tabella a indirizzamento diretto, con un puntatore da

slot a oggetto, possiamo memorizzare l’oggetto nello slot stesso, risparmiando spazio.

Inoltre, spesso non serve memorizzare la chiave dell’oggetto, in quanto se abbiamo l’indice

di un oggetto nella tabella abbiamo anche la sua chiave.

Se le chiavi non sono memorizzate, dobbiamo disporre di qualche metodo per sapere se uno

slot è vuoto.

Tabelle hash

● Il grande difetto dell’indirizzamento diretto è che, se l’universo U delle chiavi è molto

grande è impossibile memorizzare una tabella T di dimensioni |U|. Inoltre, l’insieme K

​

delle chiavi effettivamente memorizzate può essere così piccolo rispetto a U che la

maggior parte dello spazio allocato per la tabella T sarebbe sprecato.

● Quando l’insieme K è molto più piccolo rispetto dell’universo U, una tabella hash

richiede molto meno spazio rispetto a una tabella a indirizzamento diretto (lo spazio

utilizzato è Θ(|K|) senza perdere il vantaggio del tempo di esecuzione che rimane

​

O(1). Il problema è che questo limite vale per il tempo medio​ , mentre

​

nell’indirizzamento diretto vale per il t empo nel caso peggiore​

.

​ ​

● Con l’indirizzamento diretto, un elemento con chiave k è memorizzato nello slot k

.

​

Con l’hashing, questo elemento è memorizzato nello slot h(k): cioè si utilizza una

​ ​ ​

funzione hash h per calcolare lo slot della chiave k

. Qui h associa l’universo U delle

​ ​

chiavi agli slot di una tabella hash​ T[0...m-1]: h:U-> {0,1,...m-1}

​ ​ ​ ​

● Diciamo che un elemento con chiave k corrisponde allo slot h(k) o che h(k) è il valore

​

hash​ della chiave k

. ​

● Il compito della funzione hash è quello di ridurre l’intervallo degli indici dell’array

​

che devono essere gestiti. Anzichè |U| valori ne gestisce solo m

, riducendo lo spazio

richiesto in memoria.

● Esiste però un problema, cioè che due chiavi possono essere associate allo stesso

​

slot, ovvero la collisione.

● La soluzione ideale sarebbe di evitare ogni collisione e si potrebbe tentare di

​

risolvere il problema con una funzione hash h casuale​

, evitando le collisioni.

Tuttavia, poichè |U| > m, ci devono essere almeno due chiavi che hanno lo stesso

valore hash; evitare collisioni è quindi impossibile. ​

● La tecnica più semplice per risolvere le collisioni è il concatenamento​

, il metodo è

l’indirizzamento aperto.

Risoluzione collisioni mediante concatenamento

​

● Nel concatenamento si pongono tutti gli elementi associati allo stesso slot in una

lista concatenata

​

● Lo slot j contiene un puntatore alla tes