i120: Oppgavesett 4

Introduksjon

Oppgave 1.1 og 1.2 til forrige ukes gruppeøvelser gikk fra en ikke-generisk implementasjon av binært tre, til det som skulle være en generisk implementasjon av ADT Binært Tre. I oppgaveteksten var det ikke presisert at for en generisk implementering skal alle parametere være enten en 'interface' eller et 'Object'. I løsningsforslaget til forrige ukes oppgave, som nå ligger ute, og som dere alle bør ta en titt på, har dog dette blitt tatt hensyn til, og vi har definert et interface bt for binære trær, samt et interface Posisjon.

I denne ukens oppgave skal vi følge en liknende utvikling fra en ikke-generisk implementasjon av en heap i oppgave 1.1, til en generisk implementasjon av en prioritetskø i oppgave 1.2.

Oppgave 1

1.1 Implementasjon av ikke-generisk heap

Skriv et Java program for en spesialisert heap hvor elementene består kun av nøkler som er positive heltall. Det binære treet til din Heap skal implementeres vha en tabell, og du skal bruke din implementasjon fra forrige ukes oppgave 1.1

I tillegg til eventuelle støttemetoder skal du implementere:

Heap(max): Lag en heap som kan lagre opptil max nøkler.
settInn(x): Sett inn nøkkel x i heap.
finnMin(): Returner minste nøkkel.
fjernMin(): Returner minste nøkkel, og fjern denne fra heap'en.

Din metode settInn(x) må anvende Upheap (se Javakode side 313 og figur side 307) og din fjernMin() må anvende Downheap (se Javakode side 313 og figur side 309).

Bruk utskriftsmetodene for binærtre-implementasjonen og tegning av den tilhørende trestrukturen for hånd for å sjekke at din heap er korrekt.

Sjekk også at implementasjonen er rask ved å bruke din heap til å sortere 10.000 tilfeldige tall:

for i=1 to 10.000 settInn(neste_tilfeldige_tall);
for i=1 to 10.000 SortertTabell[i]=fjernMin();

Bruk java.util.Random til å generere neste_tilfeldige_tall. Dokumentasjon finnes i API spesifikasjonen. F.eks kan du bruke metoden nextInt:

public int nextInt(int n): Returns a pseudorandom, uniformly distributed 
int value between 0 (inclusive) and n (exclusive).

Det betyr at følgende kode returnerer et tilfeldig tall mellom 0 og 10000

   Random randomGen = new Random();
   int tilfeldigTall = randomGen.nextInt(10000);

1.2 Implementasjon av Abstrakt DataType Prioritetskø (PQ) vha Heap

Implementer ADT PQ vha en heap med datastruktur tabell. ADT PQ skal inneholde tilsvarende metoder som i deloppgave 1.1, men vi skal nå lagre generelle objekter, og bruke en generisk Comparator for de aktuelle nøklene. For enkelhets skyld definerer vi vårt eget interface:

public interface PK{
   
    public Object fjernMin(); // returner og fjern et (element, key)-par med 
           // minste nøkkel.
    public void settInn(Object elm, Object key); // Sett inn paret (elm, key)
    public Object finnMin(); // Returner minste nøkkel.

Du skal altså gi en implementasjon

public class PKHeap implements PK{

som bl.a. skal ha en konstruktør:

   public PKHeap(Comparator c, int max)

hvor c skal kunne sammenlikne nøkkelobjektene som lagres.