Heapsort: verschil tussen versies

 

 

Het idee achter sortering door middel van heapsort is eigenlijk heel eenvoudig:

Om dit algoritme uit te kunnen voeren, is het alleen maar nodig om een heap te kunnen maken uit een rij van elementen.

 

 

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.

]|

 

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.

 

]|

 

 

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.

]|

 

 

Heapsort is een vrij efficiënt algoritme, zowel qua ruimtegebruik als qua [[complexiteitsgraad|orde van looptijd]].

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(²log(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*²log(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 implementatie in C:

</pre>

 

 

De sorteermethode van heapsort is gebaseerd op een oplossing van:

<math>Heap.A=\langle\forall i,j : i=j \mathbf{div}2 : geordend.(A.i,A.j) \rangle </math>

 

 

Men voege een nieuw element toe aan het eind van de rij die de heap bevat en confronteert het met het

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

HeapIn vanuit een lege Heap gemaakt worden.

 

 

Het te leveren element is A.0.

]|

 

 

Een groot voordeel van dit mechanisme is dat (bijna) de helft van het sorteren geschiedt

aantal wachtende activiteiten is).

 

 

Als een tabel met elementen in snel geheugen reeds bestaat en deze gesorteerd moet worden,

Het eerste deel van de slotconditie is geen kunst, het tweede was de opdracht.

 

[[Categorie:Sorteeralgoritme]]