Visa källa för Heapsort

{{databox}}

'''Heapsort''' är en instabil [[sorteringsalgoritm]]. Den sorterar ''n'' objekt med [[tidskomplexitet]] <math>O(n\log n)</math> i värsta fall. Algoritmen kan ses som en förbättring av [[urvalssortering]] där datastrukturen [[Heap (datastruktur)|heap]] utnyttjas för att snabbt kunna välja ut det största elementet i varje steg.<ref>{{Bokref|efternamn=Skiena|förnamn=Steven|titel=The Algorithm Design Manual|hämtdatum=|år=2008|sid=109}}</ref>

== Algoritmen ==
Konceptuellt genomför Heapsort två steg. I det första steget byggs en [[Heap (datastruktur)|max-heap]] upp utifrån listan som ska sorteras. Detta kan implementeras som en array som representerar ett [[binärträd]], där det största elementet finns först i arrayen.<ref name="clrs">{{Bokref |efternamn1=H Cormen|förnamn1=Thomas |efternamn2=E Leiserson|förnamn2=Charles |efternamn3=L Rivest|förnamn3=Ronald |efternamn4=Stein|förnamn4=Clifford |titel=Introduction to algorithms|hämtdatum=|år=2009|sid=160|isbn=9780262033848 |utgivare=MIT Press}}</ref>

I det andra steget så plockas det största elementet ut från heapen och flyttas till slutet av arrayen. Heapstorleken minskar sedan med ett, och den del av arrayen som ingår i heapen uppdateras för att behålla heap-egenskaperna. <ref name="clrs"/> Detta upprepas fram tills heapen är tom, varpå arrayen är indatan i sorterad ordning.

== Tidskomplexitet ==
Att bygga upp en heap i en array har tidskomplexitet <math>O(n)</math>, för en lista med storlek n. Att uppdatera en heap så att den behåller heap-egenskaperna har tidskomplexitet <math>O(\log n)</math>, för en array med storlek n. I det andra steget i algoritmen så körs uppdateringen en gång för varje element i listan som ska sorteras, vilket ger en total tidskomplexitet på <math>O(n\log n)</math>. <ref name="clrs"/>

== Källor ==
<references/>

== Externa länkar ==
* [https://rosettacode.org/wiki/Sorting_algorithms/Heapsort Implementeringar av heapsort i ett antal olika programmeringsspråk] {{En ikon}}

[[Kategori:Sorteringsalgoritmer]]