Beim Heapsort werden die zu sortierenden Schlüssel einer Folge in zwei Repräsentation betrachet:

• Feldrepräsentation: Die Folge der unsortierten Schlüssel in einem Feld die sortiert werden soll. Am Ende des Heapsorts soll diese Folge als Feld aufsteigend sortiert sein.
• Heaprepräsentation: Eine interne Repräsentation auf der die Regeln des Heapsorts angewendet werden. Diese Heaprepräsentation in der Form eines Binärbaums dient ausschließlich dem Verständnis des Betrachters

Beide Repräsentationen sind Sichten auf die gleichen Daten. Beim Heapsort werden nicht die Schlüssel in einen Binärbaum umkopiert. Die Heaprepräsentation dient nur dem Betrachter zur Verdeutlichung der Beziehung gewisser Feldpositionen.

Die Grundidee des Heapsorts besteht darin, daß an der Wurzel des Binärbaums immer der größte Schlüssel stehen muss. Diesen größten Schlüssel kann man dann dem Binärbaum entnehmen und als größtes Element der Folge benutzen. Die verbliebene unsortierte Teilfolge muss dann wieder so als ein Baum organisiert werden in dem das größte Element an der Wurzel steht. Durch sukzessives Entnehmen der verbliebenen gößten Elemente kann man die gesamte Folge sortieren.

Das Beispiel links zeigt nicht eine vollständige Sortierung der gesamten Folge.

Es zeigt nur das Einsortieren eines Elements für eine Feldstruktur die schon der Heapbedingung genügt.

Das Feld mit den N=9 Elementen wurde so vorsortiert, dass es der Heapdebingung genügt. Das Herstellen der Heapbedingung wird später erläutert.

Das Element mit dem Schlüssel 9 wird von der Spitze des Baums f[1] entfernt...

... und mit dem Wert 2 der Position N=9 getauscht. Der größte Schlüssel der Folge befindet sich jetzt auf der Position 9.

Alle Elemente ab f[9]= F[N] aufwärts sind jetzt aufsteigend sortiert.

Alle Elemente von f[1] bis f[N-1]=f[8] sind unsortiert und müssen noch sortiert werden.

Die Elemente von f[1] bis f[8] genügen auch nicht mehr der Heapbedingung. Der Wert f[1]=2 ist nicht größer als f[2]=8 oder f[3]=7