Algoritmi in podatkovne strukture 1

Napišite program v javi, ki na tri različne načine implementira vrsto s prednostjo (ang. priority queue) in v testnem razredu primerja časovno zahtevnost vseh treh izvedb. Vrsto s prednostjo je treba implementirati z :

• neurejenim poljem, 
  
• maksimalno kopico, implicitno zapisano v polju in 
  
• maksimalno psevdokopico, eksplicitno zapisano s povezanimi objekti Node. 
  

Preverjanje zahtevnosti naj izvede veliko število naključnih vstavljanj, izločanj in izpisov prvih elementov (števil), rezultat pa naj bo izražen s časom ter številom premikov in primerjav.

Na voljo so naslednji razred in vmesniki:

class CollectionException extends Exception {
    public CollectionException(String msg) {
         super(msg);
    }
}

interface Collection {
    static final String ERR_MSG_EMPTY = "Collection is empty.";

    boolean isEmpty();
    int size();
    String toString();
}

interface Queue<T> extends Collection {
    T front() throws CollectionException;
    void enqueue(T x);
    T dequeue() throws CollectionException;
}

interface PriorityQueue<T extends Comparable> extends Queue<T> {
}

Vrsta s prednostjo

Vrsta s prednostjo vsebuje elemente (objekte generičnega tipa T, ki je Comparable), ki jih je mogoče primerjati po velikosti (z metodo compareTo). Od navadne vrste se razlikuje tako, da iz vrste vedno izloči tisti element, ki je največji po prioriteti.

Tri implementacije 

Za vsako implementacijo napišite svoj razred, ki ustrezno definira notranjo strukturo in vse potrebne metode: 

• ArrayPQ za izvedbo, kjer so elementi hranjeni v neurejenem polju, 
  
• ArrayHeapPQ za implicitno izvedbo maksimalne kopice s poljem in 
  
• LinkedHeapPQ za eksplicitno izvedbo maksimalne psevdokopice s povezanimi objekti Node, ki predstavljajo vozlišča dvojiškega drevesa. 
  

Pri obeh izvedbah s poljem naj bo začetna kapaciteta 64, vendar je v primeru pomanjkanja prostora urejeno ustrezno povečevanje kapacitete polja z metodo resize, ki podvoji trenutno kapaciteto polja. Pri obeh zvedbah kopice pravilno izvedite vse tri metode (vstavljanje, izločanje in vračanje prvega elementa) glede na uporabljeno strukturo.   

Primerjava hitrosti

V testnem razredu Izziv3 izvedite primerjavo hitrosti vseh treh implementacij prioritetne vrste. V ta namen izvedite na vseh treh zaporedje enakih operacij: recimo najprej napolnite vse tri z večjim številom elementov (recimo 1000 naključnimi števili - objekti tipa Integer), nato pa izvedite še veliko (recimo 1000) zaporednih izločanj (največjega elementa), vstavljanj  (naključnih elementov) in izpisov prvih (največjih) elementov. Ob tem za vsako implementacijo izmerite čas (v ms), preštejte število premikov (= prirejanj spremenljivke tipa T) in primerjav (= klicev metode compareTo). 

Rezultat izpišite v tabelarični obliki.

Objekti: Integer

Operacije: 1000 enqueue + 1000 (dequeue+enqueue+front)

Implementacija                     Čas [ms]           Premikov             Primerjav

--------------------------------------------------------------------------------------

Neurejeno polje  (64,2x)          xx                      xx                        xx

Implicitna koplica  (64,2x)       xx                      xx                        xx

Eksplicitna kopica                     xx                      xx                        xx   

Izvedbo poskusa (število in vrsto operacij) prilagodite tako, da boste dobili nazoren rezultat.

Oddaja

Vse razrede vaše rešitve ter sliko s tabelo rezultatov oddajte na običajen način (v eni datoteki .zip) do (naslednjega) ponedeljka.