En max-heap er sortert slik at rot-noden er den største noden av alle nodene i heapen. Alle forelder-noder i heapen er større en barne-nodene sine. For Min-heap er det motsatt.
Heapsort begynner med å bygge en max-heap (Build-max-heap) av en liste med tall. Man sikrer dermed en gyldig Max-heap hvor rot-noden er den største noden i heapen.
Heapsort henter derette ut roten (det største tallet) og trekker opp en av nodene fra bunnen og setter den som ny rot. Nå er alle sub-grafene til roten en max-heap, men roten i seg selv gjør at hele treet er feil (ettersom den er av lav verdi).
Ved å kjøre max-heapify vil man nok en gang kunne hente opp det største tallet i heapen. Dette tallet kan igjen hentes ut og erstattes med et lavt tall fra bunnen av heapen.
Algoritmen utnytter altså at max-heapify alltid finner maximum i heapen og bruker dette til å sortere den originale listen.
- In-place: Ja
- Stabil: Nei, Heap sort er typisk ustabil, men kan bli implementert som stabil. Den vil vanligvis endre den relative rekkefølgen ved duplikat-verdier.
The HEAPSORT procedure takes time
$O(n \log n)$ since the call to BUILD-MAXHEAP takes time$O(n)$ and each of the$n-1$ calls to MAX-HEAPIFY takes time$O(\log n)$
| Best case | Average case | Worst case | Minne |
|---|---|---|---|
| ??? |
Heapsort bygger først en max-heap ved hjelp av Build-max-heap. Nå er det største elementet på toppen. Dette elementet hentes ut fra heapen. Den flytter så en av de minste elementene helt til toppen før den kjører Max-heapify igjen.
Max-heapify garanterer at det største elementet i heapen nok en gang kommer til toppen. Denne prosessen gjør det mulig å hente ut det største elementet i heapen hver gang.