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