Heapsort, Variante 1 (Grundgerüst)

Hierbei handelt es sich um das Grundgerüst aller Varianten.

Bitte beachten Sie, daß die Laufzeitabschätzung eines k-nären Heaps nur für 1 < k << n gilt. Die Sonderfälle k ≡ 1 und k ≈ n sollten gesondert betrachtet werden. Aus der Laufzeitabschätzung folgt, daß die minimale Anzahl der Vergleiche bei k ≡ e ≈ 3 erreicht wird. Sind Vertauschungen teurer als Vergleiche, so kann sich das ganze zu k ≡ 4.32 ≈ 4 (doppelt so teuer) verschieben. Wenn Sie also Heapsort optimal anwenden wollen, so sollten sie "k=3" oder "k=4" wählen.

Variante 1.a (iterativ)
Typ standard, k-när
Eigenschaften iterativ, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(kn) Θ(knlogkn) Ο(knlogkn)
Vergleiche (k+1)n n(klogkn-2.5) nklogkn
Vertauschungen n nlogkn (n/k+n)*logkn

heapsort(field A, int l, int r) {
  buildheap(A, l, r);
  for i:=r downto l+1 do {
    exchange(A[l], A[i]);
    heapify(A, l, l, i-1);
  }    
}

buildheap(field A, int l, int r) {
  for i:= (r-l-1) div k downto 0 do {
    heapify(A, l, l+i, r);
  }
}

heapify(field A, int l, int q, int r) {
  for ever do {
    largest:= l+k*(q-l)+1;
    if (largest <= r) then {
      for i:= largest+1 to largest+k-1 do {
        if (i <= r) and (A[i] > A[largest]) then {
          largest:= i;
        }
      }
      if (A[largest] > A[q]) then {
        exchange(A[largest], A[q]);
        q:= largest;
      } else {
        return;
      }
    } else {
      return;
    }
  }
}

Variante 1.b (halbrekursiv)
Typ standard, k-när
Eigenschaften halbrekursiv, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(kn) Θ(knlogkn) Ο(knlogkn)
Vergleiche (k+1)n n(klogkn-2.5) nklogkn
Vertauschungen n nlogkn (n/k+n)*logkn

heapsort(field A, int l, int r) {
  buildheap(A, l, r);
  heapsort2(A, l, r);
}

heapsort2(field A, int l, int r) {
  if (r > l) then {
    exchange(A[l], A[r]);
    heapify(A, l, l, r-1);
    heapsort2(A, l, r-1);
  }
}

buildheap(field A, int l, int r) {
  buildheap(A, l, r, (r-l-1) div k);
}

buildheap(field A, int l, int r, int i) {
  if (i >= 0) then {
    heapify(A, l, l+i, r);
    buildheap(A, l, r, i-1);
  }
}

heapify(field A, int l, int q, int r) {
  largest:= l+k*(q-l)+1;
  if (largest <= r) then {
    for i:= largest+1 to largest+k-1 do {
      if (i <= r) and (A[i] > A[largest]) then {
        largest:= i;
      }
    }
    if (A[largest] > A[q]) then {
      exchange(A[largest], A[q]);
      heapify(A, l, largest, r);
    }
  }
}