Wikipedia

Heapsort: verschil tussen versies

Interactief door geschiedenis bladeren
← Oudere bewerkingNieuwere bewerking →
Verwijderde inhoud Toegevoegde inhoud
VisueelWikitekst
Geen bewerkingssamenvatting
Regel 1:
'''Heapsort''' is een snel [[sorteeralgoritme]], ontwikkeld in 1964 door [[Robert W. Floyd]] en J. W. J. Williams. Het probeert, net zoals [[straight selection sort]], het grootste element van de te sorteren rij te zoeken, dit achteraan te plaatsen en zo met een minder verder te gaan tot alles op volgorde staat. Het algoritme is bijzonder efficiënt in geheugengebruik, maar is niet [[stabiliteit (sorteeralgoritme)|stabiel]].
 
== Sortering vanuit een heap ==
{{zieZie ook|zie het artikel [[heap]] voor meer informatie over de heap-datastructuur}}
 
Het idee achter sortering door middel van heapsort is eigenlijk heel eenvoudig:
 
# Begin met een rij van te sorteren elementen.
# Definieer een lege rij om de elementen in gesorteerde volgorde op te slaan
# Vorm uit de te sorteren elementen een max-heap; hierin bevindt het element met de grootste waarde zich in de wortel van de [[grafentheorie|boom]].
# Plaats dit element achterin de resultaatrij, op de achterste plaats die nog vrij is. Haal het element uit de rij van te sorteren elementen.
# Als de rij van te sorteren elementen nog niet leeg is, ga dan naar stap 3.
Regel 15:
 
== Het maken van een heap ==
 
Zoals te lezen valt in het artikel [[heap]], is het niet nodig om je in allerlei bochten te wringen om een heap te maken – een heap is dan in principe wel een boomstructuur, maar hij kan daarom toch prima opgeslagen worden in een rij (zoals een [[array]]). Als je je maar aan de heap-regel houdt.
 
Regel 23 ⟶ 22:
 
<code>
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;
]|
</code>
 
Regel 38 ⟶ 37:
 
<code>
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;
]|
</code>
 
Dit is bijna goed. Het enige dat niet klopt is dat we met de berekening van links en rechts wel eens waarden kunnen vinden die niet meer in de rij A liggen (die heeft namelijk een eindige grootte lengte.A):
 
<code>
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)
]|
</code>
 
Regel 83 ⟶ 82:
 
<code>
|[ n : integer;
|
|
n := lengte.A;
 
do i > 0 -> MaakHeap(A, n); i := i - 1
od
]|
</code>
 
Regel 95 ⟶ 94:
 
<code>
|[ 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
]|
</code>
 
== Een kleine optimalisatie ==
 
Het bovenstaande is correct, maar het maakt wel onnodig gebruik van een extra rij B. In iedere slag van het algoritme wordt namelijk precies een element definitief gesorteerd en valt dus weg uit A – dat betekent dat A altijd precies evenveel ruimte open heeft staan als er gesorteerde elementen zijn. Dus kunnen we de gesorteerde rij net zo goed meteen in A opslaan.
 
Regel 137 ⟶ 135:
 
<code>
|[ 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;
]|
</code>
 
== Efficiëntie ==
 
Heapsort is een vrij efficiënt algoritme, zowel qua ruimtegebruik als qua [[complexiteitsgraad|orde van looptijd]].
 
Regel 182 ⟶ 179:
 
== Een programmavoorbeeld ==
 
Een implementatie in C:
<code>
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;
}
</code>
 
== Alternatief -- iteratief ==
=== Sortering door middel van heaps ===
De sorteermethode van heapsort is gebaseerd op een oplossing van:
 
# Maak uit elementen in willekeurige volgorde een rij van die elementen
De sorteermethode van heapsort is gebaseerd op een oplossing van:
 
# Maak uit elementen in willekeurige volgorde een rij van die elementen
# Produceer uit die rij van elementen deze elementen in de voorgeschreven volgorde
 
onder de voorwaarde: het toevoegen respectievelijk het verwijderen van een
element in 1 en 2 geschiedt in een tijd maximaal evenredig met de logaritme van het aantal
elementen in de rij.
 
gegeven:
de voorgeschreven volgorde 'geordend.(A,B)' is een [[totale ordening]] en kan tussen willekeurige
elementen in vaste tijd worden geëvalueerd
 
De oplossing die hier gepresenteerd wordt is een rij met elementen die voldoen aan:
 
<math>Heap.A=\langle\forall i,j : 2 \times i=j \vee 2 \times i+1=j : geordend.(A.i,A.j) \rangle </math>
 
of equivalent
 
<math>Heap.A=\langle\forall i,j : i=j \mathbf{div}2 : geordend.(A.i,A.j) \rangle </math>
 
=== Het maken van een Heap uit elementen in willekeurige volgorde ===
Men voege een nieuw element toe aan het eind van de rij die de heap bevat en confronteert het met het
 
Men voege een nieuw element toe aan het eind van de rij die de heap bevat en confronteert het met het
element dat het in strijd met de voorwaarde zou kunnen brengen: A.(i DIV 2) , waar i zijn huidige positie is.
Als de heapvoorwaarde niet voldaan is verwisselen we de elementen. Dit wordt herhaald waarbij in elke slag
de index minstens halveert tot het nieuwe element de heapvoorwaarde niet meer verstoort.
Dit moet gebeuren omdat er geen lagere elementen meer zijn of het element index 0 krijgt.
Daar 0 DIV 2 = 0 en een totale ordening o.a. reflexief is geldt geordend(A.0,A.0).
Als we het onderste element van de heap altijd index 0 geven vereenvoudigt dit het programma:
 
<code>
{ 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) }
]|
</code>
 
NB. Heap.A[0:0) is triviaal geldig dus kan een Heap elementsgewijze met
HeapIn vanuit een lege Heap gemaakt worden.
 
=== Het produceren van elementen uit een Heap in de voorgeschreven volgorde ===
Het te leveren element is A.0.
 
Vervolgens moet de heap hersteld worden zodanig dat er een nieuwe A.0 is en de heap nu
Het te leveren element is A.0.
Vervolgens moet de heap hersteld worden zodanig dat er een nieuwe A.0 is en de heap nu
aan het eind een element korter is.
Dit gebeurt door A.0 te vullen met A.1 en vervolgens de nieuwe vrije plek A.i te vullen met
het element uit {A.(2*i),A.(2*i+1)} dat het eerst voor promotie naar een lagere index in aanmerking komt.
We herhalen dit tot A(2*i+1) niet meer bestaat, waarbij de index van de vrije plek per slag minstens verdubbelt.
Regel 269 ⟶ 261:
 
<code>
{ 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) }
]|
</code>
 
=== Toepassingen ===
Een groot voordeel van dit mechanisme is dat (bijna) de helft van het sorteren geschiedt
tijdens de invoerfase en de rest tijdens de uitvoerfase, en daarmee eventueel kan worden overlapt.
Dat bovendien de werkruimte-overhead O(1) (onafhankelijk van n) is, maakt de methode
aantrekkelijk voor het sorteren van hoeveelheden gegevens die de capaciteit van het snelle
random-access geheugen benadert of overstijgt.
 
Als dat laatste het geval is kunnen met de routine van een externe ongeordende rij maximaal
lange geordende externe subrijen worden geproduceerd, die vervolgens met behoud van ordening tot
langere subrijen worden samengevoegd tot de beschikbare geheugenruimte voldoende is om alle
resterende subrijen efficiënt tot de gewenste rij (op het externe medium) te combineren.
Ook is het een effectieve 'prioriteits-wachtrij' : als de activiteit met de hoogste prioriteit
de vroegste plaats in de ordening krijgt kan deze in log.n tijd geselecteerd worden. Een nieuwe
activiteit met willekeurige prioriteit kan in log.n tijd in de wachtrij worden gezet (waar n het
aantal wachtende activiteiten is).
 
Ook is het een effectieve 'prioriteits-wachtrij' : als de activiteit met de hoogste prioriteit
=== In-situ sorteren ===
de vroegste plaats in de ordening krijgt kan deze in log.n tijd geselecteerd worden. Een nieuwe
activiteit met willekeurige prioriteit kan in log.n tijd in de wachtrij worden gezet (waar n het
aantal wachtende activiteiten is).
 
=== In-situ sorteren ===
Als een tabel met elementen in snel geheugen reeds bestaat en deze gesorteerd moet worden,
Als een tabel met elementen in snel geheugen reeds bestaat en deze gesorteerd moet worden,
dat wil zeggen er is een in-situsorteerprocedure gewenst, kan dit gerealiseerd worden:
dat wil zeggen er is een in-situsorteerprocedure gewenst, kan dit gerealiseerd worden:
 
# Transformeer de Tabel van 0 tot Tabel.lengte in een heap doch met omgekeerde van de gewenste volgorde.
# Plaats de uit de heap geproduceerde elementen in de aan het eind vrijkomende plaatsen.
 
indien een oplopende ordening gewenst is:
 
<code>
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) }
]|
</code>
 
Het eerste deel van de slotconditie is geen kunst, het tweede was de opdracht.
 
Regel 343 ⟶ 334:
 
<code>
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;
}</code>
 
[[Categorie:Sorteeralgoritme]]
 
[[no:Sorteringsalgoritme#Heap sort]]
Overgenomen van "https://nl.wikipedia.org/wiki/Heapsort"