From:        Mika K Karlstedt <karlsted@cs.Helsinki.FI>
Date:        Tue, 8 May 2001 09:50:18 +0300 (EEST)

Tehtävä 3. Keko-operaatiot

Tehtävän esimerkki-ratkaisut löytyvät verkosta. Metodit insert ja
deleteMin ovat suoraan Wiklan kurssimateriaalista ja makeToHeap ja
valutaAlas ovat muunnoksia luvusta 6.5 (kekojärjestäminen).

Metodista insert ja deleteMin sai 2 pistettä kummastakin ja 
makeToHeap oli 4 pisteen arvoinen. Tehtävistä menetti pisteen
jos ei ollut käyttänyt vertailussa compareTo-metodia. Mutta muista
pienistä virheistä ei juurikaan rangaistu.

Metodissa makeToHeap sai 2 pistettä jos käytti silmukkaa, jossa
insert-metodilla lisättiin alkiot uuteen kekoon, mutta 0 pistettä
jos vain järjesti taulukon (esim. kuplajärjestämisellä).

Seuraavassa esimerkkikoodi:

///////////////////////////////////////////////////////////////////////
//                                                Tietorakenteet  K2000
//                                                 Arto Wikla  9.3.2000
// Binäärikeon taulukkototeutus
//
// julkinen vakio: public static int DEFAULTMAXSIZE
//
// konstruktorit:
//
//     public Keko() luo oletuskokoisen keon 
//
//     public Keko(int koko) luo pyydetyn kokoisen keon             
//
// aksessorit:
//
//     public  boolean insert(Comparable alkio)
//             lisää parametrina saadun olion kekoon; metodi palauttaa
//             true, jos lisäys onnistui, false, jos keko oli täynnä 
//
//     public  Comparable deleteMin()
//             palauttaa arvonaan viitteen keon pienimpään alkioon ja
//             poistaa tämän alkion keosta 
//
//     public  makeToHeap(Comparable[] taulu)
//             tekee Comparable-taulukosta keon aikavaatimuksena
//             O(n)
//
//     private valutaAlas(Comparable[] taulu, int i, int koko)
//             valuttaa indeksissä i olevan alkion alas paikalleen
//             keossa. Huom! Keko alkaa indeksistä 0.
//
///////////////////////////////////////////////////////////////////////

public class Keko {

  public static int DEFAULTMAXSIZE=10;

  private Comparable[] puu;
  private int koko;

  public Keko() {
    this.puu  = new Comparable[DEFAULTMAXSIZE+1]; // 0:s tyhjä
    this.koko = 0;
  }

  public Keko(int koko) {
    if (koko < 0) 
      koko = 0;
    this.puu  = new Comparable[koko+1]; // 0:s tyhjä
    this.koko = 0;
  }

  public Keko(Comparable[] array, int koko) {
      int i;

      this.puu = new Comparable[koko+1];
      for(i = 0; i < koko; i++)
	  puu[i+1] = array[i];
      this.koko = 0;
  }

  public boolean insert(Comparable alkio) {

    if (koko == DEFAULTMAXSIZE)   // kaikki käytetty
      return false;

    ++koko;           // uusi lehti
    int aukko = koko;

    while ( aukko > 1 && alkio.compareTo(puu[aukko/2])<0) {
      puu[aukko] = puu[aukko/2];  // suurempi siirretään alaspäin
      aukko = aukko/2;            // aukko etenee vanhempaan
    }

    puu[aukko] = alkio;
    return true;        // lisäys onnistui
  }

  public Comparable deleteMin() {

    if (koko == 0)
      return null;

    Comparable pienin = puu[1];
    puu[1] = puu[koko];       // uusin lehti juureen;
    --koko;                   // voitaisiin nullata poistettu lehti...

    int tutkittava = 1;  // juuri

    while (2*tutkittava <= koko) {  // on vielä lapsia

      int lapsi = 2*tutkittava; // vasen lapsi

      if (lapsi != koko && puu[lapsi].compareTo(puu[lapsi+1]) > 0) 
         // vasen lapsi on lapsista suurempi, otetaan siis oikea lapsi
        ++lapsi;
 
      if (puu[tutkittava].compareTo(puu[lapsi]) > 0) {
         // tutkittava on pienempaa lasta suurempi, vaihdetaan
        Comparable apu = puu[tutkittava];
        puu[tutkittava] = puu[lapsi];
        puu[lapsi] = apu;
      }
      else      // loppu on oikeassa järjestyksessä
        break; 

      tutkittava = lapsi;
    }

    return pienin;
  }

  public static void makeToHeap(Comparable[] taulu) {
    for (int i = taulu.length/2; i >= 0; --i)   // tehdään keoksi
      valutaAlas(taulu, i, taulu.length);
  }

  private static void valutaAlas(Comparable[] taulu, int i, int n) {
    int lapsi;
    Comparable tmp;

    for (tmp = taulu[i]; 2*i+1 < n; i=lapsi) {
      lapsi = 2*i+1;  // vasen lapsi! (taulukko alkaa 0:sta)
      if ((lapsi != n - 1) && (taulu[lapsi].compareTo(taulu[lapsi + 1]) > 0))
        ++lapsi;
      if (tmp.compareTo(taulu[lapsi]) > 0)
        taulu[i] = taulu[lapsi];
      else
        break;
    }
    taulu[i] = tmp;
  }
}