Пирамидальная сортировка (сортировка кучей, 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.\)

function heapsort(data[], count)
{
    heapify(data, count);
    end = count - 1;
    while (end > 0)
    {
        swap(data[0], data[end]);
        --end;
        siftDown(data, 0, end);
    }
}
function heapify(data[], count) 
{
    start = parentIndex(count - 1);
    while (start >= 0)
    {
        siftDown(data, start, count - 1);
         --start;
    }       
}
 

        

function siftDown(data[], start, end)
{
    root = start;
    while (leftChildIndex(root) <= end)
    {
        child = leftChildIndex(root);
        temp = root;
        if (data[temp] < data[child])
        {
            temp = child;
        }
        if (child + 1 <= end && data[temp] < data[child + 1])
        {
            temp = child + 1;
        }
        if (temp == root)
        {
            return;
        }
        else
        {
            swap(data[root], data[temp]);
            root = temp;
        }
    }
}
function heapsort(data[], count)
{
    heapify(data, count);
    end = count - 1;
    while (end > 0)
    {
        swap(data[0], data[end]);
        --end;
        heapify(data, end);
    }
}
function heapify(data[], count) 
{
    end = 1;
    while (end < count)
    {
        siftUp(data, 0, end);
        ++end;
    }       
}
 

        

function siftUp(data[], start, end)
{
    child = end;
    while (child > start)
    {
        parent = parentIndext(child);
        if (data[parent] < data[child])
        {
            swap(data[parent], data[child]);
            child = parent;
        }
        else
        {
            return;
        }
    }
}