allgemeines Sortierverfahren zum Sortieren von n Elementen.

Das Verfahren besteht aus zwei Schritten. Im ersten Schritt wird ein Heap aufgebaut, der die n Elemente der Eingabefolge enthält. Um die sortierte Liste zu erhalten, wird im zweiten Schritt der Heap schrittweise wieder abgebaut, indem jeweils die Wurzel des Heaps gelöscht wird, in der das kleinste Element des Heaps steht, und die Heap-Eigenschaft (Heap) wiederhergestellt wird.

Das Verfahren benötigt zum Sortieren von n Elementen höchstens \(c\cdot n\cdot [{\mathrm{log}}_{2}n]\) Schritte für eine von n unabhängige Konstante c.