strutture dati e laboratorio ii esercitazione n°13 heap massimo
TRANSCRIPT
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