Lidt om algoritmen:
Heap sort opbygger en heap, der hele tiden returnerer den største værdi.
En heap er en trælignende struktur, bestående af noder og forbindelser mellem dem.
En node kan have null, en eller to child noder.
En heap kan godt implementeres på et array, hvis for hver node på position i, har sine child noder på position 2i+1 og 2i+2.

For at have en gyldig heap følgende to ting skal være gyldige:
1. rod noden skal have den største værdi.
2. alle child noder's værdi skal være mindre eller lig deres parent.

Den første del af sorteringen går ud på at konvertere arrayet til en gyldig heap.
Herefter får hver node en position højt i heapen, hvor den så "falder" ned gennem heapen til den når sin endelige position.
Så snart heapen er lavet er sorteringen rimeligt simpel og indeholder kun to trin:
1. Byt den sidste node ud med rode, så den største værdi kommer til at ligge sidst i arrayet.
2. Flyt den nye rod ned gennem heapen til den når sin endelige position.

Disse to trin gentages indtil hele arrayet er sorteret.

Hastighed:
O(n log n)

Eksempel:
Sourcekode til eksempel:
SortAlgorithm.java
MyHeapSort.java

Eksemplet er implementeret på et array.
MyHeapSort.java indeholder metoderne sort( int[] a ), samt metoden downheap( int a[], int marker, int length ), som udfører sorteringen.
I sort metoden er der to trin.
Det første er forløkken, hvor heapen bliver bygget op. Dette sker i kaldet til metoden downheap. I do-while løkken tælles der ned gennem arrayet og roden i heapen flyttes til den sidste plads i arrayet. Herefter genopbygges heapen ved kaldet til metoden downheap. Den nye heap rod flyttes så til den næstsidste plads i arrayet o.s.v. ind til hele arrayet er sorteret.