Heap-Sort ist ein vergleichsbasierter Sortieralgorithmus. Er hat seinen Namen von der im Algorithmus verwendeten Heap-Datenstruktur. Heap ist eine binärbaumbasierte spezielle Datenstruktur. Sie hat die folgenden zwei Eigenschaften: Es ist ein vollständiger Binärbaum, bei dem alle Ebenen gefüllt sind, außer der letzten. Die letzte kann teilweise gefüllt sein, aber alle Knoten sind so weit links wie möglich. Alle Elternknoten sind kleiner/größer als ihre beiden Kinderknoten. Wenn sie kleiner sind, wird der Heap als min-heap bezeichnet, und wenn sie größer sind, wird der Heap als max-heap bezeichnet.