Oppgave 2

  public void leggInn(T verdi)
  {
    int k = ++antall;                  // posisjon for ny node

    if (k == 1)
    {
      rot = new Node<>(null);     // null som forelder
      rot.verdi = verdi;
    }
    else
    {
      Node<T> p = rot, q = null;         // hjelpepeker
      int n = Integer.highestOneBit(k >> 1);

      while (n > 0)
      {
        q = p;
        p = (n & k) == 0 ? p.venstre : p.høyre;
        n >>= 1;  // bitforskyver n
      }

      p = new Node<>(q);    // q som forelder
      if ((k & 1) == 0) q.venstre = p;
      else q.høyre = p;

      while (q != null && comp.compare(verdi,q.verdi) < 0)
      {
        p.verdi = q.verdi;
        p = q;
        q = q.forelder;
      }

      p.verdi = verdi;

    }
  }

Oppgave 3

  public T kikk()
  {
    if (tom()) throw new NoSuchElementException("Køen er tom!");
    return rot.verdi;
  }

Oppgave 4

  public String toString()
  {
    if (tom()) return "[]";

    StringBuilder s = new StringBuilder();
    s.append('[');

    Kø<Node<T>> kø = new TabellKø<>();
    kø.leggInn(rot);

    while (!kø.tom())
    {
      Node<T> p = kø.taUt();
      s.append(p.verdi).append(',').append(' ');
      if (p.venstre != null) kø.leggInn(p.venstre);
      if (p.høyre != null) kø.leggInn(p.høyre);
    }

    // har nå et komma og et mellomrom for mye
    s.delete(s.length() - 2, s.length());
    s.append(']');

    return s.toString();
  }

Oppgave 5

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

    Node<T> p = rot;                   // hjelpepeker
    T min = rot.verdi;                 // minst verdi i roten

    int k = antall;                    // hjelpevariabel
    antall--;                          // en verdi tas ut

    if (k == 1)
    {
      rot = null;                      // treet har kun en verdi
      return min;
    }

    int n = Integer.highestOneBit(k >> 1);

    while (n > 0)
    {
      p = (n & k) == 0 ? p.venstre : p.høyre;
      n >>= 1;  // bitforskyver n
    }

    // p er siste node og skal fjernes

    T temp = p.verdi;                  // denne skal omplasseres

    Node<T> q = p.forelder;

    if ((k & 1) == 0) q.venstre = null;
    else q.høyre = null;

    // starter i roten og går ned minimumsgrenen
    p = rot;
    while (p.høyre != null)            // p har to barn
    {
      p = comp.compare(p.venstre.verdi, p.høyre.verdi) <= 0
          ? p.venstre : p.høyre;
      p.forelder.verdi = p.verdi;
    }

    if (p.venstre != null)             // p kan ha et venstre barn
    {
      p = p.venstre;
      p.forelder.verdi = p.verdi;
    }

    // starter nederst i minimumsgrenen og går oppover
    q = p.forelder;

    while (q != null && comp.compare(temp,q.verdi) < 0)
    {
      p.verdi = q.verdi;
      p = q;
      q = q.forelder;
    }

    p.verdi = temp;                    // temp har blitt omplassert

    return min;                        // returnerer minste verdi
  }

Oppgave 6

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

    // må finne verdien - leter i nivåorden

    Kø<Node<T>> kø = new TabellKø<>();
    Node<T> p = rot;
    kø.leggInn(p);

    boolean funnet = false;

    while (!kø.tom() && !funnet)
    {
      p = kø.taUt();
      if (comp.compare(p.verdi,verdi) == 0) funnet = true;

      if (p.venstre != null) kø.leggInn(p.venstre);
      if (p.høyre != null) kø.leggInn(p.høyre);
    }

    if (!funnet) return false;   // verdi ligger ikke i køen

    Node<T> pp = p;  // verdi ligger i noden pp

    int k = antall;
    antall--;

    Node<T> q = pp.forelder;

    if (kø.tom())  // pp er den siste i nivåorden
    {
      if (q == null) rot = null;
      else if ((k & 1) == 0) q.venstre = null;
      else q.høyre = null;

      return true;
    }

    // må finne den siste, dvs. den som har posisjon antall

    int n = Integer.highestOneBit(k >> 1);
    p = rot;

    while (n > 0)
    {
      p = (n & k) == 0 ? p.venstre : p.høyre;
      n >>= 1;  // bitforskyver n
    }

    // p er siste node og skal fjernes

    T temp = p.verdi;  // denne skal omplasseres

    q = p.forelder;

    if ((k & 1) == 0) q.venstre = null;
    else q.høyre = null;

    // starter i pp og går ned minimumsgrenen

    p = pp;
    while (p.høyre != null)   // p har to barn
    {
      p = comp.compare(p.venstre.verdi, p.høyre.verdi) <= 0
          ? p.venstre : p.høyre;
      p.forelder.verdi = p.verdi;
    }

    if (p.venstre != null)   // p kan ha et venstre barn
    {
      p = p.venstre;
      p.forelder.verdi = p.verdi;
    }

    // starter nederst i minimumsgrenen og går oppover
    q = p.forelder;

    while (q != null && comp.compare(temp,q.verdi) < 0)
    {
      p.verdi = q.verdi;
      p = q;
      q = q.forelder;
    }

    p.verdi = temp;  // temp har blitt omplassert

    return true;   // vellykket fjerning
  }

Oppgave 7

  int[] a = Tabell.randPerm(1000000);

  PrioritetsKø<Integer> kø = BinTrePrioritetsKø.lagKø();

  long tid = System.currentTimeMillis();

  for (int k : a) kø.leggInn(k);
  while (!kø.tom()) kø.taUt();

  tid = System.currentTimeMillis() - tid;

  System.out.println(tid);