Heapsort

Heapsorti algoritmis on järgmised etapid:^{[1] [2]}

1. Sisendandmetest tuleb luua täiuslik kahendkuhi.
2. Nüüd on suurim liige kuhja juurelement (massiivi esimene element). Eemalda suurim liige, asendades see kuhja viimase liikmega (kuhja viimane liige on massiivi sorteerimata osa viimane element). Kuhja suurus vähenes ühe võrra (eemaldatud kuhja suurimast liikmest sai sorditud massiivi osa esimene element).
3. Vaheta juurelement oma suurima väärtusega alamtipuga, kuni kuhi vastab kuhja tingimusele (iga tipu väärtus on alamtippude omast suurem või sellega võrdne).
4. Jätka 2. etapist algavaid tegevusi, kuni kuhjas on üks liige.

Olgu { 6, 5, 3, 1, 8, 7, 2, 4 } massiiv, mida tahame sortida. Kõigepealt kuhjastame massiivi ja siis hakkame sortima.

Kahendkuhja loomise ajaline keerukus on ${\displaystyle O(\log n)}$ . Juurelemendi oma suurima väärtusega alamtipuga vahetamine, kuni kuhi vastab kuhja tingimusele, on ajalise keerukusega ${\displaystyle O(n)}$ . Kokku tuleb Heapsorti ajaliseks keerukuseks ${\displaystyle O(n\log n)}$ . See ajaline keerukus on nii keskmisel kui ka halvimal juhul.^[3]

Heapsorti mahuline keerukus on ${\displaystyle O(1)}$ .^[4]

Mestimissortimisel ajaline keerukus nii keskmisel kui ka halvimal juhul on ${\displaystyle O(n\log n)}$ , mahuline keerukus on aga ${\displaystyle O(n)}$ . Seetõttu eelistatakse Heapsorti mestimissortimisele siis, kui sortimiseks kuluv mälumaht on oluline.^[3]

Kiirsortimise keskmiseks ajaliseks keerukuseks on ${\displaystyle O(n\log n)}$ , aga üldiselt on see ikkagi kiirem kui Heapsort oma väiksema konstantse teguri tõttu. Kiirsortimise halvimaks ajaliseks keerukuseks on aga ${\displaystyle O(n^{2})}$ ja halvimaks mahuliseks keerukuseks ${\displaystyle O(\log n)}$ . Seetõttu on Heapsort parem sortimisalgoritm siis, kui halvim ajaline ja mahuline keerukus on olulised.^[3]