Heapsort, Variante 2 (Original, binär)

Hierbei handelt es sich um die Original-Variante.

Variante 2.a (iterativ)
Typ standard, binär
Eigenschaften iterativ, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(n) Θ(nlogn) Ο(nlogn)
Vergleiche 3n n(2logn-3) 2nlogn
Vertauschungen n n(logn-1) 3/2n*logn

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 2 downto 0 do {
    heapify(A, l, l+i, r);
  }
}

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

Variante 2.b (halbiterativ)
Typ standard, binär
Eigenschaften halbiterativ, in-place, instabil, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(1) Θ(logn) Ο(logn)
Laufzeit Ω(n) Θ(nlogn) Ο(nlogn)
Vergleiche 3n n(2logn-3) 2nlogn
Vertauschungen n n(logn-1) 3/2n*logn

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 2 downto 0 do {
    heapify(A, l, l+i, r);
  }
}

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


Heapsort, Variante 2