Zuerst wird ein Max-Heap aufgebaut. Anschließend wird das größte Element wiederholt ans Ende des Arrays verschoben. Array und Baum zeigen dabei jederzeit dieselben Elemente.
i liegt das linke Kind bei
2*i + 1 und das rechte Kind bei 2*i + 2.
Nur die Elemente links von der gestrichelten Grenze gehören noch zum Heap.
Rechts davon wächst der bereits sortierte Bereich.