Oppgave 5

Hvis antall er et partall, så er sammenligningen 2*k < antall identisk med k < antall/2. Men ikke hvis antall er et oddetall. Se f.eks. på det høyre treet i Figur 5.3.3 b). Der er antall lik 13. Dermed vil k = 6 slippe gjennom 2*k < antall siden 2*6 er mindre enn 13. Men k = 6 vil ikke slippe gjennom k < antall/2 siden 13/2 er lik 6 (heltallsdivisjon) og 6 er ikke mindre enn 6.

Dette betyr at hvis vi bruker while (k < antall/2) vil løkken kunne stoppe en node for tidlig. Dvs. at noden med posisjon k vil etterpå kunne ha både to og ett barn. Det kan vi imidlertid teste på. Dermed kan metoden minimumsGrenen kodes slik:

  public String minimumsGrenen()
  {
    StringBuilder s = new StringBuilder();
    s.append('[');

    if (antall > 0) s.append(heap[1]);  // treet er ikke tomt

    int k = 1;
    while (k < antall/2)           // så lenge k har to barn
    {
      k *= 2;                      // går til venstre
      if (comp.compare(heap[k + 1], heap[k]) < 0) k++;
      s.append(',').append(' ').append(heap[k]);
    }

    if (2*k <= antall)             // k har barn
    {
      s.append(',').append(' ');   // komma og mellomrom
      k *= 2;

      // finner det minste hvis det er to barn
      if (k < antall && comp.compare(heap[k + 1], heap[k]) < 0) k++;

      s.append(heap[k]);
    }
    s.append(']');

    return s.toString();
  }

Vi kan gjøre de samme endringene i metoden taUt:

  public T taUt()
  {
    if (tom()) throw new NoSuchElementException("Køen er tom!");

    T min = heap[1];                   // den minste ligger øverst
    T verdi = heap[antall];            // skal omplasseres

    heap[antall] = null;               // for resirkulasjon
    antall--;                          // en verdi mindre i køen    

    int k = 1;                         // nodeposisjon
    int halvparten = antall/2;         // istedenfor antall/2

    while (k < halvparten)             // så lenge k har to barn
    {
      k <<= 1;                         // til venstre ved å doble k

     // hvis høyre barn k + 1 er minst, setter vi k dit, dvs. k++
     if (comp.compare(heap[k + 1], heap[k]) < 0) k++;

      heap[k >>> 1] = heap[k];         // forskyver oppover
    }

    if (2*k <= antall)                 // k har barn
    {
      k *= 2;                          // går til venstre barn

      if (k < antall && comp.compare(heap[k + 1], heap[k]) < 0) k++;

      heap[k/2] = heap[k];               // forskyver oppover
    }

    heap[0] = verdi;                   // blir vaktpost

    while (comp.compare(heap[k/2],verdi) > 0)
    {
      heap[k] = heap[k/2];             // trekker verdien nedover
      k /= 2;                          // k går opp til forelderen
    }
    heap[k] = verdi;                   // verdi skal ligge i posisjon k    

    return min;                        // returnerer minste verdi
  }

Oppgave 6

If-setningen etter første while-løkke i taUt-metoden kan fjernes hvis while-løkken kodes slik som nedenfor. Ulempen er at at vi får en ekstra sammenligning, dvs. k < antall i hver eneste runde av while-løkken. Men k < antall er enten alltid sann eller eventuelt usann siste gang (nederst i grenen). Med andre ord blir koden litt mindre effektiv.

  while ((k << 1) <= antall)          // så lenge k har minst ett barn
  {
    k <<= 1;                         // til venstre ved å doble k
    if (k < antall && comp.compare(heap[k + 1], heap[k]) < 0) k++;
    heap[k >>> 1] = heap[k];         // forskyver oppover
  }

Hvis vi i tillegg bruker teknikken fra Oppgave 5, kan koden effektiviseres noe. Da blir den slik:

  int k = 1;                         // nodeposisjon
  int halvparten = antall/2;         // istedenfor antall/2

  while (k <= halvparten)            // så lenge k har minst ett barn
  {
    k <<= 1;                         // til venstre ved å doble k
    if (k < antall && comp.compare(heap[k + 1], heap[k]) < 0) k++;
    heap[k >>> 1] = heap[k];         // forskyver oppover
  }

Oppgave 7

Oppgave 8

  public String[] grener()
  {
    Liste<String> liste = new TabellListe<>();
    StringBuilder s = new StringBuilder("[");
    if (!tom()) grener(1, liste, s);

    String[] grener =
      new String[liste.antall()];           // oppretter tabell

    int i = 0;
    for (String gren : liste)
      grener[i++] = gren;                   // fra liste til tabell

    return grener;                          // returnerer tabellen
  }

  private void grener(int k, Liste<String> liste, StringBuilder s)
  {
    T verdi = heap[k];
    int n = verdi.toString().length(); // lengden på verdi

    if (2*k > antall)  // bladnode
    {
      liste.leggInn(s.append(verdi).append(']').toString());

      // må fjerne det som ble lagt inn sist - dvs. n + 1 tegn
      s.delete(s.length() - n - 1, s.length());
    }
    else
    {
      s.append(heap[k]).append(',').append(' ');  // legger inn n + 2 tegn
      if (2*k <= antall) grener(2*k, liste, s);
      if (2*k < antall) grener(2*k + 1, liste, s);
      s.delete(s.length() - n - 2, s.length());   // fjerner n + 2 tegn
    }
  }

Oppgave 9

  public boolean taUt(T verdi)         // skal legges i klassen HeapPrioritetsKø
  {
    if (verdi == null) return false;   // køen har ikke nullverdier

    T omplasseres = heap[antall];      // skal omplasseres
    heap[antall] = null;               // for resirkulasjon
    antall--;                          // en verdi mindre i køen  

    // sjekker om det er siste verdi som skal tas ut
    if (comp.compare(verdi,omplasseres) == 0) return true;

    int k = 1; for (; k <= antall; k++)  // leter etter verdien som skal ut
    {
      if (comp.compare(verdi,heap[k]) == 0) break;
    }

    if (k > antall) return false;      // fant ikke verdi

    // k er nå posisjonen til verdien som skal tas ut
    while ((k << 1) < antall)          // så lenge k har to barn
    {
      k <<= 1;                         // til venstre ved å doble k

      // hvis høyre barn k + 1 er minst, setter vi k dit, dvs. k++
      if (comp.compare(heap[k + 1], heap[k]) < 0) k++;

      heap[k >>> 1] = heap[k];         // forskyver oppover
    }

    if (2*k == antall)                 // har k et barn?
    {
      k *= 2;                          // går til venstre barn
      heap[k/2] = heap[k];             // forskyver oppover
    }

    // verdien som skal omplasseres settes inn på rett sortert
    // plass i grenen som ender i noden med posisjon k

    heap[0] = omplasseres;             // blir vaktpost

    while (comp.compare(heap[k/2],omplasseres) > 0)
    {
      heap[k] = heap[k/2];             // trekker verdien nedover
      k /= 2;                          // k går opp til forelderen
    }

    heap[k] = omplasseres;             // verdi skal ligge i posisjon k      

    return true;
  }