|
<pre>
MaakHeap (A : rij, i : integer) =
|[ links, rechts : integer;
|
|
links, rechts := 2 * i, 2 * i + 1; {zie artikel heap}
if MAX(A.i, A.links, A.rechts) = A.rechts -> A.i, A.rechts := A.rechts, A.i
[] MAX(A.i, A.links, A.rechts) = A.links -> A.i, A.links := A.links, A.i
[] MAX(A.i, A.links, A.rechts) = A.i -> skip {hier hoeft niets mee te gebeuren}
fi;
]|
</pre>
<pre>
MaakHeap (A : rij, i : integer) =
|[ links, rechts : integer;
|
|
links, rechts := 2 * i, 2 * i + 1; {zie artikel heap}
if MAX(A.i, A.links, A.rechts) = A.rechts -> A.i, A.rechts := A.rechts, A.i;
MaakHeap(A, rechts)
[] MAX(A.i, A.links, A.rechts) = A.links -> A.i, A.links := A.links, A.i;
MaakHeap(A, links)
[] MAX(A.i, A.links, A.rechts) = A.i -> skip {hier hoeft niets mee te gebeuren}
fi;
]|
</pre>
<pre>
MaakHeap (A : rij, i : integer) =
|[ links, rechts : integer;
grootste : integer;
|
|
links, rechts := 2 * i, 2 * i + 1; {zie artikel heap}
if (links <= lengte.A) AND (A.links > A.i) -> grootste := links
[] (links > lengte.A) OR (A.links <= A.i) -> grootste := i
fi
;
;
if (rechts <= lengte.A) AND (A.rechts > A.grootste) -> grootste := rechts
fi
;
;
if not (grootste = i) -> A.i, A.grootste := A.grootste, A.i;
MaakHeap(A, grootste)
]|
</pre>
<pre>
|[ n : integer;
|
|
n := lengte.A;
do i > 0 -> MaakHeap(A, n); i := i - 1
od
]|
</pre>
<pre>
|[ var N = ...; {lengte.A = N}
A : rij[1..N] van integer; {A is onze initiële rij}
B : rij[1..N] van integer; {B is onze resultaatrij}
n : integer;
MaakHeap (A : rij, i : integer) =
|[ var links, rechts : integer;
grootste : integer;
|
|
links, rechts := 2 * i, 2 * i + 1; {zie artikel heap}
if (links <= N) AND (A.links > A.i) -> grootste := links
[] (links > N) OR (A.links <= A.i) -> grootste := i
fi
fi
;
;
if (rechts <= N) AND (A.rechts > A.grootste) -> grootste := rechts
fi
fi
;
;
if not (grootste = i) -> A.i, A.grootste := A.grootste, A.i;
MaakHeap(A, grootste)
]|
|
|
n := N;
do i > 0 -> MaakHeap(A, n); i := i - 1
od;
do N > 1 -> B.N, A.1 := A.1, A.(N-1);
N := N - 1;
MaakHeap(A, 1);
od;
B.1 := A.1
]|
</pre>
<pre>
|[ const N = ...; {lengte.A = N}
var G : integer; {grootte.A = G}
A : rij[1..N] van integer; {A is onze initiële rij}
B : rij[1..N] van integer; {B is onze resultaatrij}
n : integer;
MaakHeap (A : rij, i : integer) =
|[ var links, rechts : integer;
grootste : integer;
|
|
links, rechts := 2 * i, 2 * i + 1; {zie artikel heap}
if (links <= G) AND (A.links > A.i) -> grootste := links
[] (links > G) OR (A.links <= A.i) -> grootste := i
fi
fi
;
;
if (rechts <= G) AND (A.rechts > A.grootste) -> grootste := rechts
fi
fi
;
;
if not (grootste = i) -> A.i, A.grootste := A.grootste, A.i;
MaakHeap(A, grootste)
]|
|
|
n := N;
do i > 0 -> MaakHeap(A, n); i := i - 1
od;
G := N;
do G > 0 -> A.G, A.1 := A.1, A.G;
G := G - 1;
MaakHeap(A, 1);
od;
]|
</pre>
Een implementatie in C:
<source lang="c">
void heapsort(int invoer[],int lengte){
int t;
if(lengte<=1) return;
//sorteer heap
for(int i=1;i<lengte;i++){
//indien i groter is dan zijn ouder, wissel ze dan en check dan met zijn grootouder enzovoort
//ouder van i is (i-1)/2
//kinderen van i zijn i*2+1 en i*2+2
for(int j=1;invoer[(i-j+1)/j]>0 && invoer[(i-j+1)/j] > invoer[(i-2*j+1)/(2*j)] ;j*=2){
t=invoer[(i-j+1)/j]; invoer[(i-j+1)/j]=invoer[(i-2*j+1)/(2*j)]; invoer[(i-2*j+1)/(2*j)]=t;
}
}
}
}
//wissel top met laatste element, top staat nu goed, en heapsort de rest
t=invoer[0]; invoer[0]=invoer[lengte-1]; invoer[lengte-1]=t;
heapsort(invoer,lengte-1);
return;
}
</source>
<pre>
{ vereist : Heap.A[0:n) }
{ vereist : A.lengte > n }
HeapIn ( var A : rij(elem), var n : integer, in : elem, geordend : (elem,elem)->Boolean)
|[ var i,j : integer;
{ n=N EN Heap.A[0:n) }
A.n:=in;
i,j,n:=n DIV 2,n,n+1;
do ¬geordend.(A.i,A.j) -> A:swap(i,j); i,j:=i DIV 2,i od;
{ n=N+1 EN Heap.A[0:n) }
]|
</pre>
<pre>
{ vereist : Heap.A[0:n) }
{ vereist : A.lengte >= n > 0 }
HeapUit (var A : rij(elem), var n : integer, var uit : elem, geordend : (elem,elem)->Boolean)
|[ var i,j :integer;
{ n=N+1 EN Heap.A[0:n) }
uit:= A.0;
A.0:=A.1;
i,j=1,2;
do j < n
-> if geordend.(A.j,A.(j+1)) -> A.i:=A.j; i,j:=j,2*j
[] geordend.(A.(j+1),A.j) -> A.i:=A.(j+1);i,j:=j+1,2*(j+1)
fi
od;
i,j,n:=i DIV 2,i,n-1;
A.j:=A.n;
do ¬geordend.(A.i,A.j) -> A:swap(i,j); i,j:=i DIV 2,i od;
{ n=N EN Heap.A[0:n) }
]|
</pre>
<pre>
HeapSort (var A : rij(elem))
|[ var n : integer;
aflopend(elem l,elem r)->Boolean |[ l>=r ]|;
{ aflopend.A = <Ai,j : i <= j : aflopend(A.i,A.j)> } { oplopend.A = <Ai,j : i <= j : aflopend(A.j,A.i)> } n:=0;
{ Heap.A[0:n) }
do n < A.lengte -> HeapIn(A,n,A.n,aflopend) od;
{ n = A.lengte}
{ Heap.A[0:n) EN oplopend.A[n:A.lengte) }
do n > 0
-> |[var temp : elem;
HeapUit(A,n,temp,aflopend);
A.(n+1):=temp
]|
]|
od
{ Heap.A[0:0) EN oplopend.A[0:A.lengte) }
]|
</pre>
<source lang="c++">
void heapsort(int array[], int aantal)
{
{
int array2[];
for(int teller=aantal;teller >0;teller--)
{
{
int index = 0;
for(int teller2=0;teller2<=teller;teller2++)
{
{
if(array[index]<array[teller2]) {
{
index=teller2;
}
}
}
}
array2[teller]=array[index];
delete(array+index);
}
}
return;
}
}</source>
[[Categorie:Sorteeralgoritme]]
| 