Appunti per l'esame di Algoritmica, FRANCESCO ROMANI

HEAPSORT(A)

1. BUILD-MAX-HEAP(A)

2. for i=A.lenght downto 2

3. swap(A[1],A[i])

4. A.heap-size--

5. MAX-HEAPIFY(A,1)

(la figura pag 135 mostra il funzionamento di HEAPSORT)

La procedura impiega un tempo O(n lg n), in quanto la chiamata in riga 1 impiega O(n) e ciascuno delle n-1 alla riga 5 ne impiega O(lg n).

6.5 Code di priorità

Heap Sort è un eccellente algoritmo, ma può essere battuto da un buon quicksort. Però la struttura dati heap ha svariati usi, ad esempio la coda di priorità. Una coda di priorità è una struttura dati che serve a mantenere un insieme S di elementi, ciascuno con un valore associato detto chiave. Una coda di max-priorità supporta le seguenti operazioni:

• INSERT(S,x), inserisce x nell’insieme S.
• MAXIMUM(S), restituisce l’elemento di S con la chiave più grande.
• EXTRACT-MAX(S), rimuove e restituisce l’elemento di S con la chiave più grande.
• INCREASE-KEY(S,x,k), aumenta il valore della

chiave di x al nuovo valore k, il quale sisuppone essere grande almeno quanto il valore corrente della chiave di x.(per la coda di min-priorità è tutto l’inverso).

Possiamo utilizzare un heap per implementare una coda di priorità. In una data applicazione, come la programmazione dei lavori o la simulazione controllata da eventi, gli elementi di coda di priorità corrispondono a oggetti dell’applicazione. Spesso è necessario determinare quale oggetto dell’applicazione corrisponde ad un dato elemento della coda e viceversa. Pertanto, quando un heap viene utilizzato per implementare una coda, spesso occorre memorizzare in ogni elemento un handle (aggancio) che generalmente corrisponde all’indice dell’elemento. Analogamente occorre memorizzare un handle all’elemento (el→handle, handle→el). Ovviamente, poiché gli elementi durante l’heap vengono spostati, è utile aggiornare man mano gli indici.

interessati.Adesso descriveremo le implementazioni per le operazioni di una coda di max-priorità(similari sono quelli per la min-priorità):

HEAP-MAXIMUM(A)

1. return A[1]

Questa impiega, banalmente, un tempo di Θ(1) (inutile spiegare perché)

HEAP-EXTRACT-MAX(A)

1. if A.heap-size < 1

2. error “underflow dell’heap”

3. max=A[1]

4. A[1]=A[A.heap-size]

5. A.heap-size=A.heap-size-1

6. MAX-HEAPIFY(A,1)

7. return max

Il tempo di esecuzione di questa procedura è pari a O(lg n) (la chiamata a MAX-HEAPIFY)in quanto tutte le altre stringhe sono costanti.

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

1. if key<A[i]

2. error “la nuova chiave è più piccola della corrente”

3. A[i]=key

4. while i>1 && A[Parent(i)]<A[i]

5. swap(A[i], A[Parent(i)])

6. i=Parent(i)

L’elemento della coda di priorità la cui chiave va aumentata è identificato da un indice inell’array. Innanzitutto, la procedura aggiorna la chiave

prima espande il max-heap aggiungendo all'albero una nuova foglia la cui chiave è INT_MIN. Poi nella riga 3 chiama l'incremento della chiave per impostare, appunto, la chiave di questo nuovo nodo al suo valore corretto e mantenere dunque la proprietà del max-heap.

Il tempo di esecuzione della procedura con un heap di n elementi è O(lg n). In sintesi, un heap può svolgere ciascuna operazione con le code di priorità nel tempo O(lg n) su un insieme di dimensione n.

11. HASHING (pag 209-219)

Una tavola hash è una struttura dati efficace per implementare i dizionari. Sebbene la ricerca di un elemento in una tabella hash richieda un tempo Θ(n), nel caso peggiore, l'hashing è molto utile e abbastanza efficace. Infatti, sotto ipotesi ragionevoli, impiega un O(1) per cercare un elemento in una tavola hash.

Una tavola hash è una generalizzazione della nozione più semplice di array ordinario. L'indirizzamento diretto in

Un array sfrutta la possibilità di esaminare una posizione dello stesso in tempo O(1). Possiamo permetterci l'indirizzamento diretto quando possiamo permetterci di allocare un array che ha una posizione per ogni chiave possibile. Quando il numero di chiavi effettivamente memorizzate è piccolo rispetto al totale di chiavi possibili, la tavola hash diventa una valida alternativa al classico indirizzamento dell'array, in quanto una tavola hash usa un indirizzamento proporzionale al numero di chiavi memorizzate. Anziché usare la chiave come indice dell'array, la useremo per calcolare appunto l'indice.

11.1 Tavole a indirizzamento diretto

L'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}, con m non

molto grande. Supponiamo inoltre che due elementi non possano avere la stessa posizione. Per rappresentare l'insieme dinamico, utilizziamo un array o tavola a indirizzamento diretto, che indicheremo con T[0,m-1], dove ogni posizione o cella corrisponde ad una chiave di U. (figura 11.1, pag 210 spiega il funzionamento).

Le operazioni di dizionario da implementare sono:

DIRECT-ADDRESS-SEARCH(T,k)
1. return T[k]

DIRECT-ADDRESS-INSERT(T,x)
1. T[x.key]=x

DIRECT-ADDRESS-DELETE(T,x)
1. T[x.key]=NIL //equivale a NULL

Ciascuna di queste operazioni impiega un tempo O(1). Per alcune applicazioni, gli elementi dell'insieme dinamico possono essere memorizzati nella stessa tavola a indirizzamento diretto. Ovvero, anziché memorizzare la chiave e i dati satelliti di un elemento in un oggetto esterno alla tavola di indirizzamento diretto, con un puntatore da una cella della tavola all'oggetto, possiamo memorizzare l'oggetto nella cella stessa, risparmiando così spazio. Spesso non

è nemmeno necessario memorizzare la chiave dell’oggetto, poiché seabbiamo l’indice di un oggetto, abbiamo anche la chiave. Se però non memorizziamo lechiavi, dobbiamo prevedere un modo per indicare che la cella è vuota.

11.2 Tavole hash

La difficoltà dell’indirizzamento è ovvia, poiché se U è troppo grande, memorizzare unatavola T di |U| elementi può essere quasi impossibile, considerata la limitatezza dimemoria di un computer medio. Per di più, è probabile che l’insieme K di elementimemorizzati sia talmente piccolo che la maggior parte dello spazio allocato verrebbesprecato.

Quando K ha un numero di chiavi nel dizionario molto più piccolo dell’intero U, una tavolahash richiede meno spazio rispetto ad una tavola ad indirizzamento diretto. Infatti lo spaziopuò essere ridotto a Θ(|K|) senza perdere il vantaggio di ricerca in O(1). La differenza stache però

questo limite vale per il caso medio, mentre in quella a indirizzamento diretto era per il caso peggiore.

Mentre con l'indirizzamento diretto, una chiave k veniva memorizzata in una cella k, con l'hashing questo elemento viene memorizzato nella cella h(k): utilizziamo dunque una funzione hash h per calcolare la chiave dell'elemento k. Qui h associa U alle celle di una tavola hash T[0,m-1] dove m è la dimensione della tavola, la quale è h : U → {0, 1 , . .., m -1} più piccola di U.

Diremo generalmente che la cella h(k) è il valore hash della chiave k (o anche che k è mappato nella cella h(k)).

Il compito della funzione hash è quello di ridurre l'intervallo degli indici e di conseguenza la dimensione dell'array (avere dunque dim=m e non più |U|). Però spesso c'è spesso un problema, ossia due o più chiavi possono essere mappate in una stessa cella e ciò genererebbe una

cosiddetta collisione. Le collisioni spesso generano dei conflitti e dunque è consigliabile trovare dei metodi per evitarli o comunque ridurli al minimo. Un metodo appunto è fare in modo di evitarli totalmente utilizzando un'opportuna funzione hash h. Un'idea sarebbe ad esempio quella di costruire una funzione h che sembri "casuale", evitando le collisioni e dunque i conflitti (una funzione hash h però è di tipo deterministico, dunque per un input uno ed un solo output h(k)).

Poiché |U| > m, è impossibile non ottenere almeno un conflitto, almeno due chiavi avranno lo stesso valore hash. Dunque, per quanto sia possibile ridurre le collisioni, è sempre buona cosa generare una funzione per risolvere tali conflitti.

- Risoluzione delle collisioni mediante concatenamento: nel concatenamento poniamo tutti gli elementi che sono associati alla stessa cella in una lista concatenata. Ad esempio assumiamo una cella j alla quale