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.
TESTO ESERCITAZIONE
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
-> 1
Eliminare il primo nome
-> 2
Visualizzare la lista
-> 3
Terminare il programma
-> 0
facendo corrispondere una funzione ad ogni scelta.
LE CODE CON PRIORITÀ
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).
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.
[1]
[2]
[4]
10
14
7
12
8
[5]
6
[6]
[3]
INSERIMENTO IN UN HEAP MASSIMO
[1]
[2]
[4]
14
20
2
15
10
[5]
1
[6]
[3]
INSERIMENTO IN UN HEAP MASSIMO
[1]
[2]
[4]
14
20
2
15
10
[5]
5
[6]
[3]
INSERIMENTO IN UN HEAP MASSIMO
[1]
[2]
[4]
14
20
5
15
10
[5]
2
[6]
[3]
INSERIMENTO IN UN HEAP MASSIMO
[1]
[2]
[4]
14
20
2
15
10
[5]
21
[6]
[3]
INSERIMENTO IN UN HEAP MASSIMO
[1]
[2]
[4]
14
20
21
2
15
10
[5]
221
[6]
[3]
INSERIMENTO IN UN HEAP MASSIMO
[1]
[2]
[4]
14
21
20
15
10
[5]
2
[6]
[3]
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
ALGORITMO:
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;
}
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
[1]
[2]
[4]
14
20
2
15
10
[5]
[3]
CANCELLAZIONE IN
UN HEAP MASSIMO
[1]
[2]
[4]
14
15
10
2
[3]
CANCELLAZIONE IN
UN HEAP MASSIMO
[1]
[2]
[4]
14
10
15
2
[3]
CANCELLAZIONE IN
UN HEAP MASSIMO
[1]
[2]
[4]
10
14
15
2
[3]
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