Oppgave 1

Den nye versjonen av lagMaksimumsheap er litt mer effektiv enn den gamle, men det er den delen av heapsortering der maksimumsheapen sorteres hvor mesteparten av arbeidet skjer. Derfor vil forbedringen på heapsorteringen som helhet kun være helt marginal.

  public static void heapsortering(int[] a)
  {
    // første del: a gjøres om til en maksimumsheap - ny versjon

    int lengde = a.length;

    for (int k = (lengde - 2)/2; k >= 0; k--)
    {
      int verdi = a[k];                       // skal omplasseres
      int forelder = k;                       // hjelpevariabel
      int halvveis = lengde / 2;              // hjelpevariabel

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

        if (barn + 1 < lengde                 // er det et høyre barn?
          && a[barn + 1] > a[barn]) barn++;   // høyre barn er størst

        if (verdi >= a[barn]) break;          // verdi skal på plass forelder

        a[forelder] = a[barn];                // forskyver oppover
        forelder = barn;                      // forelder går ned
      }

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

    // andre del: maksimumsheapen å sorteres - gammel versjon

    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      
    }
  }