Oppgave 1

  int[] a = {};
  int[] b = {1};
  int[] c = {1,2};
  int[] d = {2,1};

  lagMaksimumsheap(a); System.out.println(Arrays.toString(a));
  lagMaksimumsheap(b); System.out.println(Arrays.toString(b));
  lagMaksimumsheap(c); System.out.println(Arrays.toString(c));
  lagMaksimumsheap(d); System.out.println(Arrays.toString(d));

  // Utskrift

  // []
  // [1]
  // [2, 1]
  // [2, 1]

Oppgave 2

  public static void lagMaksimumsheap(int[] a)
  {
    for (int i = 1; i < a.length; i++)         // starter i posisjon 1
    {
      int k = i;                               // k er en hjelpevariabel
      int verdi = a[i];                        // verdi er en hjelpevariabel

      if (verdi > a[0])                        // skal ligge øverst
      {
        while (k > 0)
        {
          a[k] = a[(k - 1) / 2];               // trekker ned fra forelder
          k = (k - 1) / 2;                     // oppdaterer k
        }
      }
      else                                     // verdi <= a[0]
      {
        while (verdi > a[(k - 1) / 2])         // sammenligner med forelder
        {
          a[k] = a[(k - 1) / 2];               // trekker ned fra forelder
          k = (k - 1) / 2;                     // oppdaterer k
        }
      }

      a[k] = verdi;                            // rett sortert plass for verdi
    }
  }

Oppgave 3

Med n = 1 blir det 1 maksimumsheap. Det er heapen;

[1]

Med n = 2 blir det også 1 maksimumsheap. Det er heapen:

[2, 1]

Med n = 3 blir det 2 forskjellige maksimumsheaper. Det er heapene:

[3, 1, 2]
[3, 2, 1]

Med n = 4 blir det 3 forskjellige maksimumsheaper. Det er heapene:

[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

Med n = 5 blir det 8 forskjellige maksimumsheaper. Det er heapene:

[5, 3, 4, 1, 2]
[5, 3, 4, 2, 1]
[5, 4, 1, 2, 3]
[5, 4, 1, 3, 2]
[5, 4, 2, 1, 3]
[5, 4, 2, 3, 1]
[5, 4, 3, 1, 2]
[5, 4, 3, 2, 1]

Vi kan bruke ideen i den rekursive perm-metoden til å generere alle permutasjoner av tallene fra 1 til n, kalle metoden lagMaksimumsheap for hver permutasjon og lagre resultatet i f.eks. en datastruktur som TreeSet. Da må vi imidlertid lage en komparator som ordner permutsjoner. Da vil en TreeSet ikke registrere duplikater.

  public static void perm(int[] a, int k, Set<int[]> s)
  {
    if (k == a.length-1)
    {
      int[] b = a.clone();
      lagMaksimumsheap(b);
      s.add(b);
    }
    else
    for (int i = k; i < a.length; i++)
    {
      Tabell.bytt(a,k,i);
      perm(a,k+1,s);
      Tabell.bytt(a,k,i);
    }
  }

  public static int antallMaksimumsheaper(int n)
  {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = i + 1;  // tallene fra 1 til n

    class Comp implements Comparator<int[]>  // en komparator
    {
      public int compare(int[] a, int[] b)
      {
        for (int i = 0; i < a.length; i++)
        {
          if (a[i] != b[i]) return a[i] - b[i];
        }
        return 0;  // a == b
      }
    }

    Set<int[]> s = new TreeSet<>(new Comp());  // en TreeSet

    perm(a,0,s);

    return s.size();
  }

  public static void main(String[] args)
  {
    for (int n = 1; n <= 10; n++)
    {
      System.out.println(antallMaksimumsheaper(n));
    }
  }

  // Utskrift:
  // 1
  // 1
  // 2
  // 3
  // 8
  // 20
  // 80
  // 210
  // 896
  // 3360

La H(n) være antallet forskjellige maksimumsheaper som inneholder n forskjellige tall (f.eks. tallene fra 1 til n). I en maksimumsheap som inneholder tallene fra 1 til n, må n ligge i rotnoden. La v og h være antallet noder i henholdsvis venstre og høyre subtre. Da kan ethvert utvalg på h stykker blant tallene fra 1 til n − 1 ligge i høyre subtre og hvert slikt utvalg gir H(h) forskjellige maksimumsheaper. Venstre subtre har v verdier som gir H(v) forskjellige maksimumsheaper. Dermed får vi flg.formel:

  H(n) = B(n − 1,h)*H(v)*H(h)

der B(n − 1,h) er binomialkoeffisienten.

En maksimumsheap er et komplett binærtre. Tallene 2⁰ = 1, 2¹ = 2, 2² = 4, 2³ = 8, 2⁴ = 16, osv. kalles 2-potenser. La k være den største 2-potensen som er mindre enn eller lik n. Hvis f.eks. n = 10, blir k = 2³ = 8. La videre m = n − k/2 og v og h antallet noder i henholdsvis venstre og høyre subtre. Da gjelder flg. regel:

• hvis m < k, så er v = m og h = k/2 − 1
• og ellers v = k − 1 og h = n − k

Vi lager først en metode for binomialkoeffisienten og så en for H(n):

  public static int B(int n, int k)  // binomialkoeffisienten
  {
    if (k < 0 || n < k)
      throw new IllegalArgumentException("Ulovlig parameter!");

    if (k == 0) return 1;

    int m = n;

    for (int i = 1; i < k; i++)
    {
      m *= (n - i);
      m /= (i + 1);
    }

    return m;
  }

  public static int H(int n)
  {
    if (n < 2) return 1;
    int k = Integer.highestOneBit(n);
    int m = n - k/2;

    if (m < k) return B(n-1,k/2 - 1)*H(k/2 - 1)*H(m);
    else return B(n-1,n-k)*H(n-k)*H(k-1);
  }

Hvis n blir stor, blir det oversvømmelse i datatypen int. Men det går bra opp til 16:

  public static void main(String[] args)
  {
    for (int n = 1; n <= 16; n++)
    {
      System.out.printf("n = %2d  antall = %-10d\n", n, H(n));
    }
  }

  // Utskrift:
  // n =  1  antall = 1         
  // n =  2  antall = 1         
  // n =  3  antall = 2         
  // n =  4  antall = 3         
  // n =  5  antall = 8         
  // n =  6  antall = 20        
  // n =  7  antall = 80        
  // n =  8  antall = 210       
  // n =  9  antall = 896       
  // n = 10  antall = 3360      
  // n = 11  antall = 19200     
  // n = 12  antall = 79200     
  // n = 13  antall = 506880    
  // n = 14  antall = 2745600   
  // n = 15  antall = 21964800  
  // n = 16  antall = 108108000 

Oppgave 4

Dette kan vises generelt, men vi nøyer oss her med å se på to konkrete verdier av n.

1. Hvis n = 10 (et partall), får vi først 2*(k + 1) < 10. Det er det samme som k < 4. Det andre uttrykket blir k < (10 − 1)/2 (obs: heltallsdivisjon) som også gir k < 4.
2. Hvis n = 9 (et oddetall), får vi først 2*(k + 1) < 9 som er det samme som 2*k < 7. Dette er oppfylt hvis og bare hvis k < 4. Det andre uttrykket blir k < (9 − 1)/2 som er lik k < 4.

Oppgave 5

Hvis n er antallet noder i maksimumsheapen, vil noden med posisjon k ha minst ett barn hvis k < n/2. Hvis den sammenligningen brukes i while-løkken, må en så sjekke om k da har to barn eller ikke:

  public static void sorterMaksimumsheap(int[] a)
  {
    for (int n = a.length - 1; n > 0; n--)  // n er siste node
    {
      int verdi = a[n];                        // siste verdi
      a[n] = a[0];                             // den største flyttes bakerst

      int k = 0;                               // en nodeposisjon
      int halvveis = n/2;                      // hjelpevariabel

      while (k < halvveis)                     // så lenge k har minst ett barn
      {
        int barn = 2*k + 1;                    // venstre barn til k

        if (barn + 1 < n                       // har k et høyre barn
            && a[barn+1] > a[barn]) barn++;    // finner maksimumsgrenen

        if (verdi >= a[barn]) break;           // plassen er funnet

        a[k] = a[barn];                        // forskyver oppover     
        k = barn;                              // flytter k til barnet
      }

      a[k] = verdi;                            // rett sortert plass for verdi      
    }
  }

Oppgave 6

  public static void heapsortering(int[] a)
  {
    for (int i = 1; i < a.length; i++)         // starter i posisjon 1
    {
      int k = i;                               // k er en hjelpevariabel
      int verdi = a[i];                        // verdi er en hjelpevariabel

      // (k - 1)/2 er forelder til k

      if (verdi > a[0])                        // skal verdi øverst?     
      {
        while (k > 0)
        {
          a[k] = a[(k - 1) >> 1];              // trekker ned fra forelder
          k = ((k - 1) >> 1);                  // oppdaterer k
        }
      }
      else
      {
        while (verdi > a[(k - 1) >> 1])        // sammenligner med forelder
        {
          a[k] = a[(k - 1) >> 1];              // trekker ned fra forelder
          k = ((k - 1) >> 1);                  // oppdaterer k
        }
      }
      a[k] = verdi;                            // rett sortert plass for verdi
    }

    for (int n = a.length - 1; n > 0; n--)
    {
      int verdi = a[n];            // den bakerste i maksimumsheapen

      a[n] = a[0];                 // den største flyttes bakerst

      int k = 0;                   // en nodeposisjon
      int m = (n - 1)/2;           // stoppverdi

      while (k < m)                // så lenge k har to barn
      {
        k = (k << 1) + 1;          // k går til venstre barn
        if (a[k+1] > a[k]) k++;    // finner maksimumsgrenen

        a[(k-1) >> 1] = a[k];      // forskyver oppover
      }

      if (2*(k + 1) == n)          // k har kun et venstre barn
      {
        k = 2*k + 1;               // k går til venstre barn
        a[(k-1)/2] = a[k];         // forskyver oppover
      }

      while (k > 0 && verdi > a[(k-1) >> 1])  // sammenligner med forelder
      {
        a[k] = a[(k-1)/2];         // trekker ned fra forelder
        k = (k-1)/2;               // oppdaterer k
      }

      a[k] = verdi;                // rett sortert plass for verdi      
    }
  }

  public static boolean erSortertStigende(int[] a)
  {
    for (int i = 1; i < a.length; i++)
      if (a[i-1] > a[i]) return false;  // ikke sortert stigende

    return true;  // a er sortert stigende
  }

  public static void sjekk(int[] a, int k, int[] feil)
  {
    if (k == a.length-1)
    {
      int[] b = a.clone();
      heapsortering(b);

      if (!erSortertStigende(b))
      {
        System.out.println("Feil: tabellen " + Arrays.toString(a) +
          "blir sortert til " + Arrays.toString(b));
        feil[0]++;
      }
    }
    else
    for (int i = k; i < a.length; i++)
    {
      Tabell.bytt(a,k,i);
      sjekk(a,k+1,feil);
      Tabell.bytt(a,k,i);
    }
  }

  public static int sorteringssjekk(int n)
  {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = i + 1;

    int[] feil = {0};

    sjekk(a,0,feil);

    return feil[0];
  }

  public static void main(String[] args)
  {
    int k = sorteringssjekk(4);
    System.out.println("Antall feil: " + k);
  }

Oppgave 7

  public static <T> void heapsortering(T[] a, Comparator<? super T> c)
  {
    for (int i = 1; i < a.length; i++)         // starter i posisjon 1
    {
      int k = i;                               // k er en hjelpevariabel
      T verdi = a[i];                          // verdi er en hjelpevariabel

      // (k - 1) / 2 er forelder til k

      if (c.compare(verdi, a[0]) > 0)          // skal verdi øverst?  
      {
        while (k > 0)
        {
          a[k] = a[(k - 1) / 2];               // trekker ned fra forelder
          k = ((k - 1) / 2);                   // oppdaterer k
        }
      }
      else
      {
        while(c.compare(verdi, a[(k - 1)/2]) > 0)  // sammenligner med forelder
        {
          a[k] = a[(k - 1) / 2];               // trekker ned fra forelder
          k = ((k - 1) / 2);                   // oppdaterer k
        }
      }
      a[k] = verdi;                            // rett sortert plass for verdi
    }

    for (int n = a.length - 1; n > 0; n--)
    {
      T verdi = a[n];              // den bakerste i maksimumsheapen

      a[n] = a[0];                 // den største flyttes bakerst

      int k = 0;                   // en nodeposisjon
      int m = (n - 1)/2;           // stoppverdi

      while (k < m)                // så lenge k har to barn
      {
        k = 2*k + 1;               // k går til venstre barn

        // finner maksimumsgrenen
        if (c.compare(a[k+1], a[k]) > 0) k++;

        a[(k - 1) / 2] = a[k];     // forskyver oppover
      }

      if (2*(k + 1) == n)          // k har kun et venstre barn
      {
        k = 2*k + 1;               // k går til venstre barn
        a[(k-1)/2] = a[k];         // forskyver oppover
      }

      while (k > 0 && c.compare(verdi, a[(k-1)/2]) > 0)
      {
        a[k] = a[(k-1)/2];         // trekker ned fra forelder
        k = (k-1)/2;               // oppdaterer k
      }

      a[k] = verdi;                // rett sortert plass for verdi      
    }
  }