Heap

Questa lezione ha come obiettivo l'implementazione della struttura di dati heap (basato sul massimo).

Seguire i seguenti passi implementativi:

1. Leggere, se necessario, lo pseudocodice spiegato nel corso di teoria.
2. Creare una classe MaxHeap che rappresenta uno heap basato sul massimo. La classe deve contenere i seguenti campi:
   • public int maxsize: dimensione massima dello heap;
   • public int heapsize: dimensione reale dello heap;
   • public int[] heap: vettore degli elementi [Suggerimento: si usino gli indici da 1 a maxsize];
   e i seguenti metodi:
   • public MaxHeap (int _maxsize). Costruttore: assegna maxsize al valore passato, heapsize a 0, e alloca il vettore heap [si usi la dimensione maxsize + 1 al fine di sfruttare gli indici da 1 a maxsize].
   • public MaxHeap (int[] a): Costruttore: costruisce lo heap a partire dal vettore di interi passato.
   • public boolean empty(). Verifica se lo heap è vuoto.
   • public boolean full(). Verifica se lo heap è pieno.
   • public int search(int i, int x). Cerca x nello heap radicato nell'indice i. Restituisce l'indice di x oppure -1 se x non esiste. [Usare una procedura ricorsiva ottimizzata sfruttando la proprietà dello heap]
   • public void insert(int x). Inserisce x nello heap.
   • public void deleteIndex(int i). Cancella l'elemento in posizione i dello heap.
   • public void delete(int x). Cancella l'elemento x dallo heap, se esiste.
   • public void modifyKey(int i, int k). Modifica la priorità dell'elemento in posizione i dello heap assegnandola al valore k.
   • public int extractMax(). Estrae il massimo dallo heap (e lo cancella).
   • public String toString(). Restituisce una visualizzazione lineare dello heap.
3. creare un metodo main che accetta i seguenti comandi da console:

   new m

   crea un nuovo heap vuoto con dimensione massima m;

   space

   restituisce il numero di elementi occupati e il numero di elementi liberi;

   insert k

   inserisce un nodo con chiave k;

   delete k

   cancella il nodo con chiave k, se esiste;

   delete index i

   cancella il nodo con indice i;

   search k

   cerca un nodo con chiave k e, se esiste, restituisce il suo indice;

   modify i k

   modifica la priorità del nodo in posizione i assegnandola al valore k;

   increase i k

   incrementa la priorità del nodo in posizione i di k unità;

   decrease i k

   decrementa la priorità del nodo in posizione i di k unità;

   pop

   rimuove il massimo e lo restituisce;

   print

   stampa lo heap (visualizzazione uni-dimensionale);

   viz

   stampa e salva in un documento di testo l'albero associato allo heap in formato GraphViz (visualizzazione bi-dimensionale);

   help

   stampa l'elenco dei possibili comandi;

   quit

   esce dal programma;

4. Approfondimento: creare una classe MinHeap che implementa uno heap basato sul minimo. [Suggerimento: modificare opportunamente la classe MaxHeap]