Um Heapsort zu implementieren verwendet man einen zweigeteiltes Array der Länge 2n.
In der linken Hälfte wird der Heap gespeichert,
in der rechten die zunächst unsortierte Elementmenge.
Die rechte Hälfte dient auch zur Speicherung der sortierten Elementfolge.
Heapsort funktioniert in einem two-stage Prozess:
mit den ersten n Schritten wird der Heap aufgebaut,
die nächsten n Schritte entnehmen jeweils ein Element.