Heapsort

Heapsort

Sorteringsalgoritm, parvis jämförelse 

Upp­täc­ka­re eller upp­fin­na­re	J. W. J. Williams
Tidpunkt för upptäckt eller upp­fin­nan­de	1964
Tids­komp­lex­i­tet i värsta fall	${\displaystyle O(n\log(n))}$
Tids­komp­lex­i­tet i bästa fall	${\displaystyle O(n\log(n))}$
Tids­komp­lex­i­tet i medel	${\displaystyle O(n\log(n))}$
Rums­komp­lex­i­tet i värsta fall	${\displaystyle O(1)}$

Heapsort är en instabil sorteringsalgoritm. Den sorterar n objekt med tidskomplexitet ${\displaystyle O(n\log n)}$ i värsta fall. Algoritmen kan ses som en förbättring av urvalssortering där datastrukturen heap utnyttjas för att snabbt kunna välja ut det största elementet i varje steg.

Algoritmen

Konceptuellt genomför Heapsort två steg. I det första steget byggs en 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.

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. 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 ${\displaystyle O(n)}$, för en lista med storlek n. Att uppdatera en heap så att den behåller heap-egenskaperna har tidskomplexitet ${\displaystyle O(\log n)}$, 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å ${\displaystyle O(n\log n)}$.

Källor

Externa länkar

• Implementeringar av heapsort i ett antal olika programmeringsspråk (engelska)