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