Куча - это всегда идеально сбалансированное, полностью заполненное дерево, которое следует за инвариантом кучи - для минимальной кучи значение узла всегда больше или равно значению каждого из его дочерних элементов.
Heapsort создает кучу из несортированных данных (время O (n)), затем многократно удаляет верхний элемент кучи (время O (lg n), поскольку куча должна поддерживаться при каждом удалении), и помещает его в массив,Примечательно, что это работает только в том случае, если оно сохраняет инвариант кучи, что требует, помимо прочего, идеальной балансировки и правильного дерева.
Двоичное дерево не является наиболее эффективным представлением кучи; статья в Википедии о двоичных кучах очень хорошо объясняет, как использовать массив для его представления. В статье о Heapsort упоминается полезная деталь: вы можете отсортировать на месте, используя пространство за пределами кучи, если используете представление массива, для построения выходного массива, потому что куча всегда балансирует иудаление элемента со временем освободит физически последнюю ячейку массива, представляющего кучу.