STRUTTURE DATI e LABORATORIO II

ESERCITAZIONE N°13

Heap massimo

TESTO ESERCITAZIONE

Gestire un insieme S di nomi come una coda con priorità. La priorità è data dall’ordinamento alfabetico, cioè un nome ha priorità più alta di un altro se esso lo precede nell’ordinamento alfabetico. Si richiede:

• l’inserimento di nuovi nomi nell’insieme S;• la cancellazione del nome con priorità maggiore dall’insieme S;• la visualizzazione di tutti i nomi dell’insieme S;• il salvataggio di tutti i nomi dell’insieme S su file all’uscita del programma;•la lettura dei nomi già esistenti dallo stesso file all’avvio del programma.

Suggerimento. Utilizzare un heap massimo per gestire la lista di nomi con priorità implementato con un array. Organizzare l’algoritmo con un menù del tipo:

Inserire un nuovo nome -> 1Eliminare il primo nome -> 2Visualizzare la lista -> 3Terminare il programma -> 0facendo corrispondere una funzione ad ogni scelta.

TESTO ESERCITAZIONE

Gli elementi di una coda con priorità hanno una chiave(key) che indica la precedenza nell’eliminazione. Si elimina l’elemento con priorità più elevata (o meno elevata).

LE CODE CON PRIORITÀ

L’ Heap non è l’unico modo di implementare una coda con priorità, ma sicuramente è il migliore.

Rappresentazione Inserimento Cancellazione

Array non ordinato (1) (n)

Lista concatenata non ordinata

(1) (n)

Array ordinato (n) (1)

Lista concatenata ordinata

(n) (1)

Heap massimo (log2n) (log2n)

HEAP MASSIMO

Definizione:

Un albero massimo(max tree) è un albero in cui il valore della chiave di ogni nodo non è minore dei valori delle chiavi dei suoi figli (se esistono). Un heap massimo è un albero binario completo.

14

12

810 6

7

[1]

[2] [3]

[6][4] [5]

INSERIMENTO IN UN HEAP MASSIMO

20

15

1014 1

2

[1]

[2] [3]

[6][4] [5]

INSERIMENTO IN UN HEAP MASSIMO

20

15

1014 5

2

[1]

[2] [3]

[6][4] [5]

20

15

1014 2

5

[1]

[2] [3]

[6][4] [5]

INSERIMENTO IN UN HEAP MASSIMO

INSERIMENTO IN UN HEAP MASSIMO

20

15

1014 21

2

[1]

[2] [3]

[6][4] [5]

20

15

1014 21

2

[1]

[2]

[6][4] [5]

20

15

1014 2

21

[1]

[2] [3]

[6][4] [5]

INSERIMENTO IN UN HEAP MASSIMO

21

15

1014 2

20

[1]

[2] [3]

[6][4] [5]

INSERIMENTO IN UN HEAP MASSIMO

INSERIMENTO IN UN HEAP MASSIMO

DICHIARAZIONI:

#define MAX_ELEMENTI 200

#define HEAP_FULL(n) (n == MAX_ELEMENTI-1)

#define HEAP_EMPTY(n) (!n)

typedef struct elemento {

int chiave;

/*altri campi*/

}elemento;

elemento heap[MAX_ELEMENTI];

int n = 0;

INSERIMENTO IN UN HEAP MASSIMO

void insert_max_heap(elemento item, int *n){

//inserisce item in un heap massimo di dimensione corrente *n

int i;

if (HEAP_FULL(*n)) {

fprintf(stderr, “L’Heap è pieno. \n”);

exit(1);

}

i = ++ (*n);

while ((i != 1) && (item.chiave > heap[i/2].chiave)){

heap[i] = heap [i/2];

i /= 2;

}

heap[i] = item;

}

}

ALGORITMO:

INSERIMENTO IN UN HEAP MASSIMO

Nell’algoritmo di inserimento per il nostro esercizio, il campo chiave è rappresentato da una stringa. Per il confronto tra nodi quindi invece degli operatori >(maggiore) o <(minore) utilizzeremo la funzione definita in string.h int strcmp( string s1, string s2).

codice

CANCELLAZIONE IN UN HEAP MASSIMO

20

15

1014

2

[1]

[2] [3]

[4] [5]

10

15

14

2

[1]

[2] [3]

[4]

CANCELLAZIONE IN UN HEAP MASSIMO

15

10

14

2

[1]

[2] [3]

[4]

CANCELLAZIONE IN UN HEAP MASSIMO

15

14

10

2

[1]

[2] [3]

[4]

CANCELLAZIONE IN UN HEAP MASSIMO

CANCELLAZIONE IN UN HEAP MASSIMO

elemento delete_max_heap(int *n) {

//cancella elemento con il valore della chiave maggiore

int padre, figlio;

elemento item, temp;

if (HEAP_EMPTY(*n)){

fprintf(stderr, “L’heap è vuoto.\n”);

exit(1);

}

//salva il valore dell’elemento con la chiave maggiore

item = heap[1];

//usa l’ultimo elemento dell’heap per modificare l’heap

temp = heap[(*n)--];

padre = 1;

figlio = 2;

}

CANCELLAZIONE IN UN HEAP MASSIMO

while (figlio <= *n) {

//trova il figlio più grande del padre corrente

if (figlio < *n) && (heap[figlio].chiave < heap[figlio+1].chiave)

figlio++;

if (temp.chiave >= heap[figlio].chiave) break;

//passa al livello inferiore

heap[padre] = heap[figlio];

padre = figlio;

figlio *= 2;

}

heap[padre] = temp;

return item;

}

CANCELLAZIONE IN UN HEAP MASSIMO

Poiché l’altezza di un heap con n elementi è log2(n+1), il ciclo while, sia per l’inserimento che per la cancellazione, verrà

ripetuto O(log2n) volte. Da qui la complessità.

Per la cancellazione da implementare nel nostro esercizio sarà necessario attuare delle modifiche per il

confronto tra le chiavi dei nodi.

codice

VISUALIZZAZIONE DI UN HEAP MASSIMO

La visualizzazione può essere implementata con vari algoritmi: preorder, inorder, postorder, level_order.

Nessuno di questi necessariamente ci visualizzerà gli elementi dell’heap ordinati.

eseguibile