Heapsort
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 stabiel.
Sortering vanuit een heap bewerken
zie het artikel heap voor meer informatie over de heap-datastructuurHet 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 boom.
- Plaats dit element achter in 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.
Om dit algoritme uit te kunnen voeren, is het alleen maar nodig om een heap te kunnen maken uit een rij van elementen.
Het maken van een heap bewerken
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.
De heap-regel is dat in iedere deelboom van de heap, de waarden van de knopen van de deelboom ten hoogste de waarde zijn van de wortel van de deelboom. Om deze regel in stand te houden, is het handig om te bedenken dat een blad van een boom op zich een deelboom is – en omdat een blad van een heap geen kinderen heeft, geldt de heap-regel dus automatisch voor alle bladeren van de heap. Stel nu dat we een manier kunnen bedenken om de heap-regel in orde te krijgen voor een deelboom waarvan de linker en rechter deelbomen van de wortel heaps zijn en alleen de wortel zelf misschien een te kleine waarde heeft. Als we een manier kunnen vinden om dat te doen, dan kunnen we uit iedere verzameling elementen een heap opbouwen door onderaan te beginnen (de bladeren van een heap zijn immers vanzelf al heaps) en ons zo een weg naar boven te werken.
Welnu, er is een manier om de heap-regel te herstellen in het hierboven beschreven geval: we zoeken uit de wortel van de deelboom, de wortel van de linker deelboom en de wortel van de rechter deelboom de grootste waarde en zetten deze in de wortel van de boom. Omdat de linker en rechter deelbomen al heaps waren, betekent dit dat de hoogste waarde van heel de deelboom nu bovenaan staat. Noemen we de rij met onze heap-in-wording erin A en de index in deze rij van de wortel van de deelboom i, dan kunnen we het bovenstaande als volgt implementeren:
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;
]|
Het enige probleem hiermee is dat we door het verwisselen van twee waarden wel eens de linker of rechter deelheap kunnen verpesten. Het element dat we in die heap zetten hoeft namelijk niet de heap-regel voor die deelheap in stand te houden. Maar geen nood: de heap die we net verpest hebben, was ooit wel een heap. En we hebben alleen maar mogelijkerwijs de wortel verpest, zodat we nu weer een boom hebben die bestaat uit twee heaps met een verkeerde wortel. En daar hadden we een oplossing voor – we hoeven alleen maar MaakHeap recursief toe te passen:
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;
]|
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):
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)
]|
De eerste heap bewerken
Het grootste gedeelte van het probleem hebben we nu opgelost. Als we twee heaps hebben, kunnen we ze met een wortel verbinden en de heap-regel herstellen. Zo kunnen we het heapsort algoritme uitvoeren door een heap te pakken en de wortel in de gesorteerde rij te zetten (de wortel is immers altijd het element met de hoogste waarde in de heap). Daarna moeten we beslissen wat de nieuwe wortel gaat worden.
Hiervoor kunnen we natuurlijk kiezen voor een van de wortels van de deelheaps die nu zonder gemeenschappelijke wortel zitten. Maar dit is lastig, want dan moeten we heel veel gaan schuiven om alle elementen weer in de vorm van een heap te krijgen (ga maar na: als je een wortel van een deelboom "omhoog trekt", dan valt de deelboom uit elkaar – dan moet je weer gaan schuiven). Een eenvoudigere methode is om een van de bladeren van de voormalige heap te kiezen en deze naar de wortelpositie te verplaatsen – een blad heeft geen kinderen, dus die kunnen we naar de top verplaatsten zonder een hoop te moeten schuiven. Natuurlijk is dan niet gegarandeerd dat we nu een heap overhouden, maar dit kunnen we met een aanroep van MaakHeap(A, 1) weer in orde maken. Bovendien heeft een keus voor een blad nog een ander voordeel waar we later op terugkomen.
Het enige probleem dat we nu nog hebben, is dat we beginnen met een totaal ongeordende rij A. Daar moeten we een initiële heap van zien te maken. Natuurlijk hebben we MaakHeap om ons te helpen; maar die helpt ons met een enkele deelboom. We moeten heel veel deelbomen in orde maken. Er zal dan ook niets anders op zitten dan voor ieder niet-blad van de boom MaakHeap aan te roepen.
Vanwege de manier waarop de boom in de rij A opgeslagen ligt (zie artikel heap), is het zo dat alle kinderen een hogere index hebben in de rij dan hun ouders. Omdat een heap een binaire boom is, geldt voor ieder niveau van de boom dat het aantal knopen in de boom op dat niveau precies 1 hoger is dan het aantal knopen in alle bovenliggende niveaus samen. Dat betekent dat A in ieder geval voor de helft uit bladeren bestaat en wel voor de helft met de hoogste indexen. We kunnen dus van onder naar boven een initiële heap opbouwen met de volgende code:
|[ n : integer;
|
n := lengte.A;
do i > 0 -> MaakHeap(A, n); i := i - 1
od
]|
Het hele heapsort algoritme ziet er nu als volgt uit:
|[ 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
;
if (rechts <= N) AND (A.rechts > A.grootste) -> grootste := rechts
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
]|
Een kleine optimalisatie bewerken
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.
We hadden eerder gezegd dat we, bij het opvullen van de wortel na iedere slag, een blad van de heap zouden kiezen. Stel nu dat we steeds het blad kiezen dat ACHTERAAN staat in de rij A. Dan is het steeds de achterste positie van A die openvalt. En toevalligerwijze is de wortel van de heap ook altijd de grootste waarde. Schuiven we die waarde op de opengevallen, achterste plek dan krijgen we uiteindelijk een perfect gesorteerde rij A, van klein naar groot. Dit ziet er als volgt uit (merk op dat we nu wel in MaakHeap op de GROOTTE van A moeten letten en niet meer puur op de LENGTE van A):
|[ 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
;
if (rechts <= G) AND (A.rechts > A.grootste) -> grootste := rechts
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;
]|
Efficiëntie bewerken
Heapsort is een vrij efficiënt algoritme, zowel qua ruimtegebruik als qua orde van looptijd.
Heapsort is een "in-place" vervangingsalgoritme, wat wil zeggen dat het algoritme het al aangemaakte geheugen van de verzameling hergebruikt. Qua ruimtegebruik is heapsort dus O(1).
De looptijd wordt bepaald door de aanroepen van MaakHeap en de doorlooptijd daarvan. De doorlooptijd van MaakHeap is lineair in de hoogte van de heap (de lengte van het langste pad van de wortel naar een blad). De heap is een binaire boom, dus de hoogte is van de boom is O(2log(N)), waarmee MaakHeap logaritmisch is in complexiteit. MaakHeap wordt in het hoofdalgoritme een keer aangeroepen voor ieder element van de invoerrij, waarmee de totale complexiteit uitkomt op O(N*2log(N)). Merk op dat het opbouwen van de initiële heap hier niets aan verandert. Ook hiervoor geldt dat de hoofdloop lineair is en de aanroepen van MaakHeap logaritmisch. Sterker nog, omdat er voor ieder hoogteniveau in de boom een maximaal aantal knopen is, kan zelfs vastgesteld worden dat de eerste opbouw van de heap lineaire tijd vergt en dus efficiënter is dan het hoofdalgoritme.
Een programmavoorbeeld bewerken
Een implementatie in 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;
}
Alternatief -- iteratief bewerken
Sortering door middel van heaps bewerken
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:
of equivalent
Het maken van een Heap uit elementen in willekeurige volgorde bewerken
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:
{ 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) }
]|
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 bewerken
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. Wij vullen A.i nu met het laatste element in de rij, dat nu potentieel niet geordend is t.o.v. A.(i DIV 2). Dit wordt op dezelfde wijze als bij het toevoegen van een nieuw element verholpen.
{ 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) }
]|
Toepassingen bewerken
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).
In-situ sorteren bewerken
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:
- 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:
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) }
]|
Het eerste deel van de slotconditie is geen kunst, het tweede was de opdracht.
Een implementatie in C++ :
|
Er wordt getwijfeld aan de juistheid van het volgende gedeelte Raadpleeg de bijbehorende overlegpagina voor meer informatie, en pas na controle desgewenst het artikel aan. |
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;
}