Corsi precedenti

Quinta Esercitazione in Laboratorio

L’argomento di questa esercitazione sono gli heap. E’ disponibile una classe MaxHeap, i cui oggetti rappresentano max-heap. La classe offre, tra gli altri, i seguenti metodi:

public class MaxHeap {
  public void insert(int k) {...}
  public int getFirst()     {...}
  public int deleteFirst()  {...}
  public boolean isEmpty()  {...}
  public boolean isFull()   {...}
  public int getSize()      {...}
}

ExtendedHeap

Progettare una struttura dati che realizzi le operazioni dichiarate nella seguente interfaccia:

public interface IExtendedHeap {
  void insert(int k);
  int getFirst();
  int deleteFirst();
  boolean isEmpty();
  int getSecond();    //Restituisce il secondo elemento più grande
  int deleteSecond(); //Elimina il secondo elemento più grande
}

Valutare il costo computazionale di ciascuna delle operazioni.

Costruire una classe Java che implementi l’interfaccia IExtendedHeap. Si suggerisce di estendere la classe MaxHeap. Collaudare la classe con opportuni test.

MinHeap attraverso MaxHeap

Costruire una classe Java che realizzi un min-heap, utilizzando un max-heap per la sua rappresentazione; valutare il costo computazionale delle operazioni del min-heap.

Collaudare la classe con opportuni test.

Come sarebbe possibile risolvere questo esercizio se, invece di chiavi intere, sia il max-heap fornito che il min-heap da implementare maneggiassero chiavi di tipo Comparable?

MedianHeap

Progettare una struttura dati che realizzi realizzi le operazioni dichiarate nella seguente interfaccia:

public interface IMedianHeap {
  void insert(int k);
  int getMedian();
  int deleteMedian();
  boolean isEmpty();
}

Per la rappresentazione della struttura si consiglia di usare congiuntamente un max-heap e un min-heap; valutare il costo computazionale di ciascuna delle operazioni.

Costruire una classe Java che implementi l’interfaccia IMedianHeap.

Si ricorda che lâ??elemento mediano di un insieme è, informalmente, lâ??elemento che â??sta in mezzoâ?. Più precisamente, se , lâ??elemento mediano è:

• , se è dispari;
• , se è pari.

Collaudare la classe con opportuni test.

Commenti dei visitatori

Accedi per lasciare commenti.