Пирамидальная сортировка (сортировка кучей, heapsort) — сортировка, которая использует логическое представление массива в виде кучи. Куча — по крайней мере в этом варианте, который называется max-heap — это двоичное (бинарное) дерево, каждый элемент которого меньше своего родителя.

heapsort() сперва вызывает функцию heapify(), которая особым образом перестраивает массив: превращает его в кучу. Изначально элементы массива располагаются так: нулевой элемент — корень, следующие два элемента — потомки корневого узла и т. д.

Поскольку самый большой элемент — корневой, то есть нулевой элемент массива, он обменивается с последним (последний элемент больше не будет перемещаться).

Но свойства кучи оказываются нарушенными, поэтому вызывается функция siftDown() (другие варианты термина sift down: bubble down, push down, fix down), которая эти свойства восстанавливает: «просеивает» элемент с вершины кучи до некоторой позиции так, чтобы в итоге восстановились свойства кучи. В альтернативном варианте элементы просеиваются наверх.

Код использует функцию parentIndex() для вычисления индекса родительского узла в куче по индексу узла \(p(i)=\left\lfloor\dfrac{i - 1}{2}\right\rfloor,\) leftChildIndex() — для вычисления индекса левого потомка: \(l(i)=2i+1,\) rightChildIndex() — для правого: \(r(i)=2i+2.\)